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

hhz6830975 · 2018-02-05 13:58:19 · 个人记录

A~~zoj 3537

B~~LightOJ 1422

设dp[i][j]为区间[i,j]的最小花费

边界条件dp[i][i]=1

考虑区间[i,j]，对于衣服i，最差情况下，[i+1][j]中不将这件衣服重复利用，那么有

而实际上，假设[i+1,j]中存在衣服k与衣服i相同，那么可以尝试用i代替k，则有

注意dp顺序为从后往前，小区间到大区间

代码：

#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

设dp[i][j]为[i,j]内最大子序列长度

先预处理所有dp[i][i+1]，然后

1.若a[i]与a[j]可以匹配，显然dp[i][j]可以取

2.对于所有dp[i][j]，都有

即两部分合并得到dp[i][j]

这里合并不需要考虑跨越两部分的括号匹配，因为这种情况在[i,j]的子区间中已经按1.的方式统计过了

代码：

#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]为将区间[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方程为：

代码：

#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

有一道类似的题，洛谷试炼场的P1220

这题的区别在于，每个点单位时间的费用是不同的，这就造成了存在后效性的问题

其实简单处理一下就可以了，只需要在每次转移的时候将未到过的点的费用一起算上

于是得到dp方程：

G~~hdu 4283

在上面的方程中，设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此时已出栈，所以也是符合要求的

代码：

#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]表示将a串[i,j]部分变成b串的最少次数

显然最差情况为单独刷，有：

若区间中存在k，使得a[i]=a[k]，那么可以先将[i,k]刷成a[i]，再刷[i+1,k]（刷[i,k]的一次在dp[i+1][k]中刷k的时候已经计算了），那么有：

这样得到的dp数组是假设两个字符串完全不相同时得到的，还需要进一步处理

设ans[i]为实际刷区间[0,i]需要的次数

如果a[i]=b[i]，那么i不用再刷，有：

如果不等，那么：