[kuangbin带你飞]专题二十二 区间DP

2018-02-05 13:58:19

A$~~$zoj 3537

B$~~$LightOJ 1422

$$dp[i][j]=dp[i+1][j]+1$$

$$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])$$

#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

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 )$$

#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

https://www.luogu.org/blog/hhz6830975/cf149d-coloring-brackets-ou-jian-dp-ji-yi-hua-sou-suo-post

E$~~$poj 1651

$$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)$$

#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

$$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

$dp[i][j]$表示假设前面没有人，区间$[i,j]$的最小值

$$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)$$

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$此时已出栈，所以也是符合要求的

#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

$$dp[i][j]=min \lbrace dp[i][k]+dp[k+1][j] \rbrace \qquad (i \leq k \leq j)$$

$$dp[i][j]=min \lbrace dp[i+1][k]+dp[k+1][j] \rbrace \qquad (i \leq k \leq j)$$

$$ans[i]=ans[i-1]$$

$$ans[i]=min \lbrace ans[j]+dp[j+1][k] \rbrace \qquad (0 \leq j<i)$$

• star
首页