[kuangbin带你飞]专题二十二 区间DP
hhz6830975
2018-02-05 13:58:19
A$~~$[zoj 3537](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3537)
B$~~$[LightOJ 1422](http://www.lightoj.com/volume_showproblem.php?problem=1422)
设$dp[i][j]$为区间$[i,j]$的最小花费
边界条件$dp[i][i]=1$
考虑区间$[i,j]$，对于衣服$i$，最差情况下，$[i+1][j]$中不将这件衣服重复利用，那么有
$$dp[i][j]=dp[i+1][j]+1$$
而实际上，假设$[i+1,j]$中存在衣服$k$与衣服$i$相同，那么可以尝试用$i$代替$k$，则有
$$dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]) \qquad (i+1 \leq k \leq j,c[i]==c[k])$$
注意dp顺序为从后往前，小区间到大区间
代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=110;
int T,n,c[maxn];
int dp[maxn][maxn];
int main(){
scanf("%d",&T);
for(int t=1;t<=T;t++){
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
dp[i][i]=1;
}
for(int i=2;i<=n;i++)
for(int j=n;j-i+1>=1;j--){
dp[j-i+1][j]=dp[j-i+2][j]+1;
for(int k=j-i+2;k<=j;k++)
if(c[k]==c[j-i+1]) dp[j-i+1][j]=min(dp[j-i+1][j],dp[j-i+1][k-1]+dp[k+1][j]);
}
printf("Case %d: %d\n",t,dp[1][n]);
}
return 0;
}
```
C$~~$[poj 2955](http://poj.org/problem?id=2955)
设$dp[i][j]$为$[i,j]$内最大子序列长度
先预处理所有$dp[i][i+1]$，然后
1.若$a[i]$与$a[j]$可以匹配，显然$dp[i][j]$可以取
$$dp[i][j]=dp[i+1][j-1]+2$$
2.对于所有$dp[i][j]$，都有
$$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]) \qquad (i \leq k<j )$$
即两部分合并得到$dp[i][j]$
这里合并不需要考虑跨越两部分的括号匹配，因为这种情况在$[i,j]$的子区间中已经按1.的方式统计过了
代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=110;
char a[maxn];
int n,dp[maxn][maxn];
int main(){
while(1){
memset(dp,0,sizeof(dp));
scanf("%s",a);
if(a[0]=='e') break;
n=strlen(a);
for(int i=0;i<n-1;i++)
if((a[i]=='('&&a[i+1]==')')||(a[i]=='['&&a[i+1]==']')) dp[i][i+1]=2;
for(int i=3;i<=n;i++)
for(int j=0;j+i-1<n;j++){
if((a[j]=='('&&a[j+i-1]==')')||(a[j]=='['&&a[j+i-1]==']')) dp[j][j+i-1]=dp[j+1][j+i-2]+2;
for(int k=j;k<j+i-1;k++)
dp[j][j+i-1]=max(dp[j][j+i-1],dp[j][k]+dp[k+1][j+i-1]);
}
printf("%d\n",dp[0][n-1]);
}
return 0;
}
```
D$~~$[CF 149D](http://codeforces.com/problemset/problem/149/D)
https://www.luogu.org/blog/hhz6830975/cf149d-coloring-brackets-ou-jian-dp-ji-yi-hua-sou-suo-post
E$~~$[poj 1651](http://poj.org/problem?id=1651)
设$dp[i][j]$为将区间$[i,j]$全部取出的最小值（包括$a[i]$和$a[j]$，两端按原来的$a[i-1]$和$a[j+1]$算）
边界条件$dp[i][i]=a[i-1] \cdot a[i] \cdot a[i+1]$
对于$dp[i][j]$，设$[i,j]$中最后取出的为$a[k]$，那么dp方程为：
$$dp[i][j]=min(dp[i][k-1]+dp[k+1][j]+a[i-1] \cdot a[k] \cdot a[j+1]) \qquad (i \leq k \leq j)$$
代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=110;
const int INF=0x7fffffff;
int n,a[maxn],dp[maxn][maxn];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n-2;i++)
for(int j=2;j+i-1<n;j++){
dp[j][j+i-1]=INF;
for(int k=j;k<=j+i-1;k++)
dp[j][j+i-1]=min(dp[j][j+i-1],dp[j][k-1]+dp[k+1][j+i-1]+a[j-1]*a[k]*a[j+i]);
}
cout<<dp[2][n-1]<<endl;
return 0;
}
```
F$~~$[zoj 3469](http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3469)
有一道类似的题，洛谷试炼场的[P1220](https://www.luogu.org/problemnew/show/P1220)
这题的区别在于，每个点单位时间的费用是不同的，这就造成了存在后效性的问题
其实简单处理一下就可以了，只需要在每次转移的时候将未到过的点的费用一起算上
于是得到dp方程：
$$dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][0]+(sumB[i]+sumB[n]-sumB[j]) \cdot (x[i+1]-x[i]) \cdot v)$$
$$dp[i][j][0]=min(dp[i][j][0],dp[i+1][j][1]+(sumB[i]+sumB[n]-sumB[j]) \cdot (x[j]-x[i]) \cdot v)$$
$$dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][0]+(sumB[i-1]+sumB[n]-sumB[j-1]) \cdot (x[j]-x[i]) \cdot v)$$
$$dp[i][j][1]=min(dp[i][j][1],dp[i][j-1][1]+(sumB[i-1]+sumB[n]-sumB[j-1]) \cdot (x[j]-x[j-1]) \cdot v)$$
G$~~$[hdu 4283](http://acm.hdu.edu.cn/showproblem.php?pid=4283)
$dp[i][j]$表示假设前面没有人，区间$[i,j]$的最小值
对于$i$这个人，考虑让他调到$k$的位置出场，那么就得到dp方程：
$$dp[i][j]=min \lbrace dp[i+1][k]+dp[k+1][j]+(sum[i]-sum[i-1]) \cdot (k-i)+(sum[j]-sum[k]) \cdot (k+1-i) \rbrace \qquad (i \leq k \leq j)$$
为什么这样能保证改变顺序的人满足栈的顺序？
所谓栈的顺序，其实就是要求对于两个同时存在于栈中的人$x$，$y$，若$x<y$，那么改变后的位置必须满足$x'>y'$
在上面的方程中，设$x=i$，则$x'=k$
对于$y$，分类讨论：
1.若$y \in [i+1,k]$，我们在之前计算$dp[i+1][k]$的子问题中，一定包含了计算$dp[y][k]$的子问题，也就默认$y' \in [y,k]$（$x$改变后为$[y-1,k-1]$），一定在$x'$前面，符合要求
2.若$y>k$，同理有$y'>x'$但$x$此时已出栈，所以也是符合要求的
代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=110;
const int INF=0x7fffffff;
int T,t=1,n,sum[maxn],dp[maxn][maxn];
int main(){
scanf("%d",&T);
while(t<=T){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&sum[i]);
dp[i][i]=0,sum[i]+=sum[i-1];
}
for(int l=2;l<=n;l++)
for(int i=1,j=i+l-1;j<=n;i++,j++){
dp[i][j]=INF;
for(int k=i;k<=j;k++)
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+(sum[i]-sum[i-1])*(k-i)+(sum[j]-sum[k])*(k+1-i));
}
printf("Case #%d: %d\n",t++,dp[1][n]);
}
return 0;
}
```
H$~~$[hdu 2476](http://acm.hdu.edu.cn/showproblem.php?pid=2476)
先假设两个字符串完全不相同，$dp[i][j]$表示将a串$[i,j]$部分变成b串的最少次数
显然最差情况为单独刷，有：
$$dp[i][j]=min \lbrace dp[i][k]+dp[k+1][j] \rbrace \qquad (i \leq k \leq j)$$
若区间中存在$k$，使得$a[i]=a[k]$，那么可以先将$[i,k]$刷成$a[i]$，再刷$[i+1,k]$（刷$[i,k]$的一次在$dp[i+1][k]$中刷$k$的时候已经计算了），那么有：
$$dp[i][j]=min \lbrace dp[i+1][k]+dp[k+1][j] \rbrace \qquad (i \leq k \leq j)$$
这样得到的dp数组是假设两个字符串完全不相同时得到的，还需要进一步处理
设$ans[i]$为实际刷区间$[0,i]$需要的次数
如果$a[i]=b[i]$，那么$i$不用再刷，有：
$$ans[i]=ans[i-1]$$
如果不等，那么：
$$ans[i]=min \lbrace ans[j]+dp[j+1][k] \rbrace \qquad (0 \leq j<i)$$