「kuangbin带你飞」专题二十二 区间DP

---

layout: post

title: 「kuangbin带你飞」专题二十二 区间DP

author: "luowentaoaa"

catalog: true

tags:

- kuangbin

- 区间DP

- 动态规划

---

传送门

B.LightOJ - 1422 Halloween Costumes

题意

按顺序参加舞会，参加一个舞会要穿一种衣服，可以在参加完一个舞会后套上另一个衣服再去参加舞会，也可以在参加一个舞会的时候把外面的衣服脱了，脱到合适的衣服，但是脱掉的衣服不能再穿，参加完全部舞会最少穿多少次衣服

题解

区间dp，dp【i】【j】表示区间i->j之间的衣服数 起始情况i->i要穿一件衣服

可以从后往前推

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

特别的如果第i 和第j个衣服是一样的

\[dp[i][j]=dp[i][j-1]
\]

然后开始在区间{I,J}之间选择K；

如果K的衣服和I的衣服一样代表 到K的时候可以把衣服脱到剩I的时候 这样就是K前面的衣服加上K->J的衣服

\[dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
\]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dp[110][110];
int a[110];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    int cnt=1;
    while(t--){
        int n;
        cin>>n;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)cin>>a[i],dp[i][i]=1;
        for(int i=n-1;i>=1;i--){
            for(int j=i+1;j<=n;j++){
                dp[i][j]=dp[i+1][j]+1;
                if(a[i]==a[j])dp[i][j]=dp[i][j-1];
                for(int k=i+1;k<j;k++){
                    if(a[i]==a[k]){
                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
                       // cout<<"i=="<<i<<"   j=="<<" dp[i][j]="<<dp[i][j]<<endl;
                    }
                }
            }
        }
        cout<<"Case "<<cnt++<<": ";
        cout<<dp[1][n]<<endl;
    }
    return 0;
}

C.POJ - 2955 Brackets

题意

给出一个的只有'(',')','[',']'四种括号组成的字符串，求最多有多少个括号满足题目里所描述的完全匹配。

题解

用dp[i][j]表示区间[i,j]里最大完全匹配数。

只要得到了dp[i][j]，那么就可以得到dp【i-1][j+1]

dp【i-1]【j+1]=dp 【i]【j]+(s[i-1]与[j+1]匹配 ? 2 : 0)

然后利用状态转移方程更新一下区间最优解即可。

\[dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])
\]

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
char s[maxn];
int dp[maxn][maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin>>s+1){
        if(s[1]=='e')break;
        memset(dp,0,sizeof(dp));
        int n=strlen(s+1);
        for(int len=2;len<=n;len++)
        for(int i=1;i<=n;i++){
            int j=i+len-1;
            if(j>n)break;
            if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']'){
                dp[i][j]=dp[i+1][j-1]+2;
            }
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
        cout<<dp[1][n]<<endl;
    }
    return 0;
}

D.CodeForces - 149D Coloring Brackets

题意

给你一个只有括号的字符串，

1,每个括号只有三种选择：涂红色，涂蓝色，不涂色。

2,每对括号有且仅有其中一个被涂色。

3,相邻的括号不能涂相同的颜色，但是相邻的括号可以同时不涂色。

题解

因为是一个合法的括号序列。

所以每个括号与之匹配的位置是一定的。

那么就可以将这个序列分成两个区间。 (L - match[L] ) (match[L]+1, R)

用递归先处理小区间，再转移大区间。

因为条件的限制，所以记录区间的同时，还要记录区间端点的颜色。

然后就是一个递归的过程。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
ll dp[800][800][3][3];
int a[110];
ll ans;
char s[800];
int match[800];
int stk[800];
void dfs(int l,int r){
    if(l+1==r){
        dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
        return;
    }
    if(match[l]==r){
        dfs(l+1,r-1);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(j!=1)dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
                if(j!=2)dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
                if(i!=1)dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
                if(i!=2)dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
            }
        }
    }
    else{
        dfs(l,match[l]);
        dfs(match[l]+1,r);
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    for(int p=0;p<3;p++){
                        if(j&&j==k)continue;
                        dp[l][r][i][p]=(dp[l][r][i][p]+(dp[l][match[l]][i][j]*dp[match[l]+1][r][k][p]%mod)%mod)%mod;
                    }
                }
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>s+1;
    int n=strlen(s+1);
    memset(match,0,sizeof(match));
    int top=-1;
    for(int i=1;i<=n;i++){
        if(s[i]=='(')stk[++top]=i;
        else match[stk[top--]]=i;
    }
    memset(dp,0,sizeof(dp));
    dfs(1,n);
    ans=0;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++){
        ans=(ans+dp[1][n][i][j])%mod;
    }
    cout<<ans<<endl;
    return 0;
}

E.POJ - 1651 Multiplication Puzzle

题意

给出N个数，每次从中抽出一个数(第一和最后一个不能抽)，每次的得分为抽出的数与相邻两个数的乘积，直到只剩下首尾两个数为止，问最小得分是多少

题解1

枚举起点和终点 ,但是这次长度要从3开始了因为中间必要取一个

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e2+50;
const int inf=0x3f3f3f3f;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int a[maxn];
int dp[maxn][maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0,sizeof(dp));

        for(int len=3;len<=n;len++){
            for(int i=1;i<=n;i++){
                int j=i+len-1;
                if(j>n)continue;
                dp[i][j]=inf;
                for(int k=i+1;k<j;k++){
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
                    //cout<<"i=="<<i<<"   j="<<j<<"   k=="<<k<<"   dp[i][j]="<<dp[i][j]<<endl;
                }
            }
        }
        cout<<dp[1][n]<<endl;
    }
    return 0;
}

题解2

记忆化搜索

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e2+50;
const int inf=0x3f3f3f3f;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int a[maxn];
int dp[maxn][maxn];
int dfs(int s,int t){
    if(dp[s][t]!=-1)return dp[s][t];
    if(t-s<=1)return 0;
    int ans=inf;
    for(int i=s+1;i<t;i++)
        ans=min(ans,dfs(s,i)+dfs(i,t)+a[s]*a[t]*a[i]);
    dp[s][t]=ans;
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,-1,sizeof(dp));
        cout<<dfs(1,n)<<endl;
    }
    return 0;
}

G.HDU - 4283 You Are the One

题意

有一个队列，每个人有一个愤怒值D，如果他是第K个上场，不开心指数就为(K-1)*D。但是边上有一个小黑屋（其实就是个堆栈），可以一定程度上调整上场程序

题意

对于区间 [x, y] 中的数字 a[x]，有可能第1个出栈，也有可能最后一个出栈，如果第k个出栈的话前i+1->k个数字要按照顺序出栈，然后a[x]出栈，[k+1,y]出栈。对于a[x]要加上a[x]×(k-i）的花费，对于[x+1, y]要加上sum(x+1, y) * (i-x+1)的额外花费。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dp[110][110];
int a[110];
int ans[110];
int sum[110];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    int cnt=1;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        memset(dp,0,sizeof(dp));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)cin>>a[i],dp[i][i]=0,sum[i]=sum[i-1]+a[i];
        for(int len=2;len<=n;len++)
        for(int i=1;i<=n;i++){
            int j=i+len-1;
            if(j>n)break;
            dp[i][j]=inf;
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],a[i]*(k-i)+(k-i+1)*(sum[j]-sum[k])+dp[i+1][k]+dp[k+1][j]);
            }
        }
        cout<<"Case #"<<cnt++<<": ";
        cout<<dp[1][n]<<endl;
    }
    return 0;
}

H.HDU - 2476 String painter

题意

给出两个长度相同的字符串a, b.对a可以进行区间更新(选择一个区间，把这个区间全部更新成相同的字符)，问要最少操作a多少次，a才能等于b？

题解

先处理一下b串 用DP存b串i到j的改变次数 然后再对a串进行状态转移。对于串b，最要是看两个相同字符之间的区间了。我们可以预处理出来改变区间[x, y]里面的字符，操作的最小次数用dp[x, y]来存储。

　　预处理完了以后，我们就可以用dp来匹配a了。ans[i] 表示 a字符区间[0, i] 与 b字符区间[0, i]相同的最小操作数目。状态转移就是：ans[i] = min (dp[0, i], ans[j] + dp【j+1】[i], ans【i-1](a[i] == b[i]))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dp[110][110];
char a[110],b[110];
int ans[110];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin>>a>>b){
        memset(dp,0,sizeof(dp));
        int n=strlen(b);
        for(int i=0;i<n;i++)dp[i][i]=1;
        for(int len=2;len<=n;len++)
        for(int i=0;i<n;i++){
            int j=i+len-1;
            if(j>=n)break;
            if(b[i]==b[j])dp[i][j]=dp[i+1][j];
            else
                dp[i][j]=dp[i+1][j]+1;
            for(int k=i+1;k<j;k++){
                if(b[k]==b[i])
                    dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
            }
        }
        ans[0]=a[0]==b[0]?0:1;
        for(int i=1;i<n;i++){
            ans[i]=dp[0][i];
            if(a[i]==b[i])ans[i]=min(ans[i],ans[i-1]);
            for(int j=0;j<i;j++)
                ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
        }
        cout<<ans[n-1]<<endl;
    }
    return 0;
}