区间dp写起来就比概率dp写起来有套路多了。
总的来说,自认为区间dp就只有三四种套路。
大致分成两种,小区间推大区间,大区间推小区间
一些平常的区间dp只要定义dp[][]两维就行,两种不同的定义方式。一种dp[i][j] 表示左端为i右端为j。另一种是dp[i][j] 表示左端为i,长度为j。两种写法对应的循环也不同。
以小区间为例
对于第一种,dp[i][j] 左端点+右端点
for(int i=n;i>=1;i--)
for(int j=i;j<=n;j++)
一般第一重循环表示右端点,第二重循环表示左端点。这样写是当要求的答案是dp[1][n] 的时候。
对于第二种,dp[i][j] 左端点+长度
for(int i=1;i<=n;i++)
for(int j=1;i+j<=n;j++)
……
一般第一重循环表示长度,第二重循环表示左端点。
还有些题目就不能直接这样写了,可能区间dp没那么明显,区间性不高。可以根据一些性质转化成区间dp。
以下是例题分析:(有题不是区间dp)
一、HDU 3280 Equal Sum Partitions
第一题就不是区间dp……区间dp第一题不是区间dp,亏我想了这么久……暴力枚举和,然后判断一下,玄学就过了。
二、HDU 4283 You Are the One
比较明显的区间dp。开始时想把一个点往相邻的区间的头尾放,然后转移就行了。然后带了一组数据发现完全错。然后发现作为一个栈,为什么只能往头尾放?栈是先进后出,那么一个点进去后,可以晚点出来。那么对于一个点,就可以插入到后面区间任意一个位置。那么转移就简单了。套用第一个模板
for(int l=1;l<=n;l++)
for(int i=1;i+l<=n;i++){
int j=i+l;
dp[i][j]=1e9;
for(int k=1;i+k-1<=j;k++)
dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+k*(cnt[j]-cnt[i+k-1])+A[i]*(k-1));
}
三、HDU 4293 Groups
这道题如果直接去想区间dp,肯定会被他的分组弄糊。反方向想,如果一个人说他前面有a个人,后面b个人,那么如果想要这个人说真话,那么他肯定要站在[a+1,n-b]这个区间内。这个显然,那么这样就划分出区间来了。可以知道对于一个区间[L,R],有很多人要站在里面,那么这个区间可能要满出来了,那就要判一下。读入的时候把这些区间求出来。问题就转化为多个有权值的区间,从中选出一些不重叠的区间使权值最大。这种问题dp只要一维就行了。
//预处理部分
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x+y<=n&&n-y-x>A[x+1][n-y])A[x+1][n-y]++;//存在区间&&区间人数足够
}
//dp部分
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
dp[i]=max(dp[i],dp[j-1]+A[j][i]);
四、HDU 4412 Sky Soldiers
求期望的区间dp。可以说dp的转移不是很难,难在预处理那一段。dp[i][j] 表示前i个点建立j个大本营要的代价。此时转移还要一个数组cost[i][j] 来辅助,表示在[i,j]区间建一个大本营的代价。那么循环一个中间点,然后往上一层转移就行。
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++){
dp[i][j]=1e9;
for(int k=0;k<i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]);
}
主要是预处理cost这个数组。如果给了降落点的范围,那么就没有那么麻烦。但是题目没给范围,那就要离散了。离散用了map,还要用迭代器,麻烦。现在讲讲不用离散的。现在要往一个区间里放一个大本营,那么就要选一个最优的位置放大本营的位置,而[i,j]又要循环过去都求一遍,那么可以一边枚举左右端点,一边选出一个最优的大本营地址。我是从后往前算的。当区间右端点固定时,最短点不断延伸,那么大本营显然会向左移动,那么每次都只要往左移动,那么大概就是n^2了。但是因为还要加map,一下子不知道怎么去重,看了一下题解,发现可以直接装起来,然后再拎出来就行了。
五、HDU 4597 Play Game
这个和取数游戏是一样的。因为两个人都是最有策略,那么只要用当前的总和减去另一个人的最有策略就行。dp要定义四维,分别是两行的左右端点。这道题其实用记忆化搜索写起来更加方便易懂。
六、HDU 4745 Two Rabbits
先肯定要把环变成一条链,只要多存一组就行了。转化为线性后,题目就变成了在一条链上求一个最长的回文子序列,因为顺时针、逆时针一样。那么转移起来就很简单了。要么从旁边传递值,要么相等加2。求答案时要注意一点,两个人的起点可能从同一个点开始,那么此时的值就是在n-1的长度里的最值再加1。
for(int i=2*n;i>=1;i--)
for(int j=i+1;j<=2*n;j++){
dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
if(A[i]==A[j])dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,max(dp[i][i+n-1],dp[i][i+n-2]+1));
七、HDU 5115 Dire Wolf
这道套一下模板,把一个区间按照一个点切开成两个区间,然后左边的加右边的再加一下附加攻击值就行。用第二个模板
for(int i=n;i>=1;i--)
for(int j=i;j<=n;j++){
dp[i][j]=1e9;
for(int k=i;k<=j;k++)//中间点切开
dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+A[k]+B[i-1]+B[j+1]);
}
八、HDU 5273 Dylans loves sequence
其实我一直不觉的只是一道区间dp。明明就是前缀和维护一下就行了……
九、HDU 5396 Expression
这个区间dp的大致想法和第七题狼那道是一样的。也是在一个区间内枚举一个点,通过这个点把整各区间分成三部分(左,此点,右),然后再累加计算就行了。我写的是记忆化搜索,因为转移的时候计算的东西很多。题目要求合并的顺序不同,尽管答案相同,也算不同方案。这样就要在存一个数组表示这一个区间的方案又是多少。然后怎么求和呢。一个点把区间分成左右两部分,左边区间的和为L,方案数为Lc,右边分别为R,Rc。那么对于左区间来说,右区间的方案数就是左区间算的次数,那么左边的和就是L* Rc。同理右边是R* Lc。累加起来就行(只限于加减,乘法只要L*R就行)。方案数要多求一个东西。Lc和Rc仅限于他们自己的区间,合并后可以左边一个右边一个,这也是不同的方案,虽然答案一样。那么还要乘一个C(l+r,l),l,r分别是左右区间的符号数。总方案数就按上面的方法变成了C(l+r,l) * Lc * Rc。
代码可以上上度娘查,我的太丑了。
十、HDU 5900 QSC and Master
也是一个比较模板的题。用一个点去切一个区间。但是切的时候要注意,因为要使两个数可以合并,除了gcd>1,还要这两个数之间的数合并完了,这还要一个数组来记录这个。
for(int i=n;i>=1;i--)
for(int j=i+1;j<=n;j++){
if(dp[i+1][j]>dp[i][j-1])dp[i][j]=dp[i+1][j];else dp[i][j]=dp[i][j-1];
Q[i][j]=-1;
for(int k=i+1;k<=j;k++)
if(Q[i+1][k-1]!=-1&&gcd(A[i],A[k])>1){
dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+1LL*V[i]+1LL*V[k]);
Q[i][k]=1;
if(Q[k+1][j]!=-1){Q[i][j]=1;break;}
}
}
我这个程序要卡常,因为gcd太慢了,如果把if语句里的gcd放在前面判断的话会T,如果先判断区间是否全部已经合并会快一些。
十一、HDU 6103 Kirinriki
这也不是区间dp。因为求的两个字符串可以看成是对称的,对称的就存在一个中间点,那么就枚举中间点。枚举中间点后,还要判断他们的值是否小于等于m。可以用尺取的方法。先把每一个对应的点求出来,然后尺取就行。中心点也分两种情况:一种是中心点是点,一种中心点不存在,但是是堆成的。贴其中一段的。
for(int i=1;i<=n;i++){
int len=min(i-1,n-i);
for(int j=1;j<=len;j++){
dp[j]=abs(str[i-j]-str[j+i]);
}
int l=1,r=1,t=dp[1];
while(r<=len){
while(l<=r&&t>m){
t-=dp[l];
l++;
}
if(ans<r-l+1)ans=r-l+1;
r++;
t+=dp[r];
}
十二、HDU 6212 Zuma
写前要处理一下。给的是01串,我们不可能直接用01串来吧?颜色相同的几个球肯定是放在一起考虑的,那么就合并起来就行了。
定义dp[i][j] 表示[i,j]区间打完要多少下。转移有三点,我只想到了两点,第三点真的想不到。
第一点:把区间[L,R]分成[L,k]和[k+1,R]两块,然后把两块的直接加起来转移进来,这要枚举一个中间点
第二点:当区间[L,R]的两端球的颜色相同时,把中间的球打掉,两边的球会往中间靠拢,当靠拢后的球大于等于三个时,直接转移,否则在往里面打一个球就行了(因为求的个数肯定大于等于1)
第三点:当区间[L,R]的两端的球的颜色相同时,可以找一个颜色相同的中间点k且此点球只有一个,把[L+1,k-1]和[k+1,R-1]的区间打掉,然后合并。此情况两边的球要保证!(A[L]==2&&A[R]==2)。原因是如果左边的球有两个,右边的球有两个的话,一往中间合并就炸掉了。例如2+1+2,左边的2+1变3,右边的1+2变3,不管怎么样都不行。但是1+1+2行,因为可以先1+1变2再2+2变4.
for(int i=n;i>=1;i--)
for(int j=i;j<=n;j++){
if(i==j){dp[i][j]=3-A[i];continue;}
dp[i][j]=1e9;
for(int k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
if((j-i)%2==1)continue;
dp[i][j]=min(dp[i][j],dp[i+1][j-1]+(A[i]+A[j]==2));
if(!(A[i]==2&&A[j]==2))
for(int k=i+1;k<j;k++)
if(A[k]==1&&(k-i)%2==0&&(j-k)%2==0)dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j-1]);
}
总结一下:
1、普通的区间dp都是很有套路的,模板就两个,按照自身习惯,再结合一下题意看写哪一个方便写哪一个。
2、区间dp常见的转移方式有:
1)两个区间合并成一个区间
2)把一个点将一个区间切成两部分,然后再把两边的加起来
3)在一个区间里枚举一个点,然后切成两部分
3、把题目中的一些条件转换成范围性的东西,然后用区间dp
4、其他:环变链:多一倍;字符串的回文或匹配:枚举中心点。