区间DP例题（持续更新）

傷城~ 2024-04-17 14:29 45阅读 0赞

# 区间DP例题（持续更新） #

**做了这几道题之后发现基本的区间dp其实也就是那回事：  
找出状态方程（基本上都长的差不多），然后用递推思维由小区间求得大区间；  
可能某些问题会有些其他处理，只需要稍微改下就行了；  
如果数据较大时，就得用到平行四边形优化**  
希望以后遇到比较简单的区间dp还是得做出来吧

<table> 
 <thead> 
  <tr> 
   <th>题目列表（题解在下面）</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><a href="http://poj.org/problem?id=3280" rel="nofollow"><font>一、poj 3280：Cheapest Palindrome</font></a></td> 
  </tr> 
  <tr> 
   <td><a href="http://poj.org/problem?id=2955" rel="nofollow"><font>二、poj 2955：Brackets</font></a></td> 
  </tr> 
  <tr> 
   <td><a href="http://acm.hdu.edu.cn/showproblem.php?pid=3506" rel="nofollow"><font>三、hdu 3506：Monkey Party</font></a></td> 
  </tr> 
  <tr> 
   <td><a href="http://acm.hdu.edu.cn/showproblem.php?pid=4283" rel="nofollow"><font>四、hdu 4283：You Are the One</font></a></td> 
  </tr> 
  <tr> 
   <td><a href="http://acm.hdu.edu.cn/showproblem.php?pid=4632" rel="nofollow"><font>五、hdu 4632：Palindrome subsequence</font></a></td> 
  </tr> 
 </tbody> 
</table>

做了几道水题之后，发现区间DP好像也有个类似于模板之类的代码：

**（以石头合并为例）**

/**以石头合并为例*/
    /**
    普通区间dp模板
    */
    //n是区间长度，dp[i][j]存从 i 到 j 区间合并的最优值
    //sum[i]    花费的前缀和(1~i的和)
    for(int i=1;i<=n;i++)
        dp[i][i]=0;
    for(int len=2;len<=n;len++)   //len选择区间长度
    {
        
        for(int i=1;i<=n-len+1;i++)    //枚举起点
        {
        
            int j=i+len-1;      //合并终点
            if(j>n)     //不可越界
                break;
            dp[i][j]=0x3f3f3f3f;
            for(int k=i;k<=j;k++)            //枚举分割点，寻找最优分割
            {
        
                int temp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                if(dp[i][j]>temp)
                    dp[i][j]=temp;
            }
        }
    }
    /**环形dp*/
    //n是区间长度，dp[i][j]存从 i 到 j 区间合并的最优值
    //sum[i]    花费的前缀和(1~i的和)
    //s[i][j]  记录从 i 到 j 的最优分割点
    for(int i=1;i<=n;i++)
    {
        
        dp[i][i]=0;
        s[i][i]=i;
    }
    for(int len=2;len<=n;len++)     //len选择区间长度
    {
        
        for(int i=1;i<=n-len+1;i++)    //枚举起点
        {
        
            int j=i+len-1;      //合并终点
            if(j>n)     //不可越界
                break;
            dp[i][j]=0x3f3f3f3f;
            for(int k=s[i][j-1];k<=s[i+1][j];k++)            //枚举分割点，寻找最优分割
            {
        
                int temp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                if(dp[i][j]>temp)
                {
        
                    dp[i][j]=temp;
                    s[i][j]=k;
                }
            }
        }
    }

[一、poj 3280：Cheapest Palindrome][poj 3280_Cheapest Palindrome]

题意：给定一字符串，可以增加或者删除某个字符，但增加或者删除字符分别对应一个代价

问：使得字符串成为回文串时，所需要的**最小代价**

一个经典的区间DP问题，估计在没接触过区间DP前，我可能毫无头绪，然后这就是一道模板题

**状态转移方程：**

if(s[i]==s[j])
        dp[i][j]=dp[i+1][j-1];
    else
        dp[i][j]=min(dp[i][j-1]+w[j],dp[i+1][j]+w[i]);

可能这里的增加和删除所对应的代价不同会有点迷，但是仔细一想其实增加和删除产生的结果是等价的，于是只需要两者取小值做为代价即可

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<map>
    using namespace std;
    int n,m;
    char s[2010];
    int dp[2010][2010];
    int main()
    {
        
        while(~scanf("%d%d",&n,&m))
        {
        
            memset(dp,0,sizeof(dp));
            map<char,int>mp;
            char ch;
            int a,b;
            scanf("%s",s);
            s[m]='\0';
            for(int i=0;i<n;i++)
            {
        
                getchar();
                scanf("%c",&ch);
                scanf("%d%d",&a,&b);
                mp[ch]=min(a,b);
            }
            for(int i=m-1;i>=0;i--)
            {
        
                for(int j=i+1;j<m;j++)
                {
        
                    if(s[i]==s[j])
                        dp[i][j]=dp[i+1][j-1];
                    else
                        dp[i][j]=min(dp[i+1][j]+mp[s[i]],dp[i][j-1]+mp[s[j]]);
                }
            }
            printf("%d\n",dp[0][m-1]);
        }
        return 0;
    }

[二、poj 2955：Brackets][poj 2955_Brackets]

题意很简单，求满足括号匹配的最长子串的长度

当时懵了，这个怎么搞嘛

后面看题解后，又感觉不是那么的难

**状态转移方程：**

if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[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+1][j]);

完整代码：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int dp[110][110];
    int main()
    {
        
        char str[110];
        while(~scanf("%s",str))
        {
        
            if(strcmp(str,"end")==0)
                break;
            int len=strlen(str);
            str[len]='\0';
            memset(dp,0,sizeof(dp));
            for(int l=0;l<len;l++)          //区间长度
            {
        
                for(int i=0;i<len-l;i++)    //区间起点
                {
        
                    int j=l+i;             //终点
                    if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[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+1][j]);
                    }
                }
            }
            printf("%d\n",dp[0][len-1]);
        }
        return 0;
    }

[三、hdu 3506：Monkey Party][hdu 3506_Monkey Party]

题意：会发现这其实就是一道**环形石头合并问题**  
主要有两种方法：**1、取模运算；2、将区间扩大至两倍**  
显然第一种比较复杂，然而第二种会由于区间过大，导致TLE，这时候就得用到**平行四边形优化**

**用s\[i\]\[j\]表示区间\[i, j\]中的最优分割点，第三重循环从区间\[i, j-1)的枚举，优化到在区间\[s\[i\]\[j-1\], s\[i+1\]\[j\]\]中枚举。  
上述原理就是“平行四边形优化”。**

完整代码：

/**环形dp*/
    //n是区间长度，dp[i][j]存从 i 到 j 区间合并的最优值
    //sum[i]    花费的前缀和(1~i的和)
    //s[i][j]  记录从 i 到 j 的最优分割点
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int w[2010];
    int dp[2010][2010];
    int sum[2010];
    int s[2010][2010];
    int main()
    {
        
        int n;
        while(~scanf("%d",&n))
        {
        
            memset(sum,0,sizeof(sum));
            memset(s,0,sizeof(s));
            memset(dp,0,sizeof(dp));
            memset(w,0,sizeof(w));
            for(int i=1; i<=n; i++)
            {
        
                scanf("%d",&w[i]);
                w[i+n]=w[i];
            }
            for(int i=1; i<=2*n; i++)
            {
        
                dp[i][i]=0;
                s[i][i]=i;
                sum[i]=sum[i-1]+w[i];
            }
            for(int len=2; len<=n; len++)   //len选择区间长度
            {
        
                for(int i=1; i<=2*n-len+1; i++)  //枚举起点
                {
        
                    int j=i+len-1;      //合并终点
                    if(j>2*n)
                        break;
                    dp[i][j]=0xffffff0;
                    for(int k=s[i][j-1]; k<=s[i+1][j]; k++)          //枚举分割点，寻找最优分割
                    {
        
                        int temp=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                        if(dp[i][j]>temp)
                        {
        
                            dp[i][j]=temp;
                            s[i][j]=k;
                        }
                    }
                }
            }
            int ans=0xffffff0;
            for(int i=1;i<=n;i++)
            {
        
                ans=min(ans,dp[i][i+n-1]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[四、hdu 4283：You Are the One][hdu 4283_You Are the One]

哭辽，感觉这道题好难啊，虽然懂了，是个咋回事，看题解后也看懂了，但是我估计我很难想到吧

题目意思很简单，就是有n个男士，每个人对应一个屌丝值Di，然后第k个顺序会获得（k-1）\*Di  
要使得获得的屌丝值最小

其中有一个栈，可以调整顺序

看到就一脸懵逼，虽然这是区间dp的练习题，但是完全不知道怎么下手

看完题解后，知道：  
**dp\[i\]\[j\]表示从第i个人到第j个人这段区间的最小花费（是只考虑这j-i+1个人，不需要考虑前面有多少人）  
那么对于dp\[i\]\[j\]的第i个人，就有可能第1个上场，也可以第j-i+1个上场。考虑第K个上场  
即在i+1之后的K-1个人是率先上场的，那么就出现了一个子问题 dp\[i+1\]\[i+k-1\]表示在第i个人之前上场的  
对于第i个人，由于是第k个上场的，那么屌丝值便是a\[i\]*(k-1)  
其余的人是排在第k+1个之后出场的，也就是一个子问题dp\[i+k\]\[j\]，对于这个区间的人，由于排在第k+1个之后，所以整体愤怒值要加上k*(sum\[j\]-sum\[i+k-1\])**

于是完整代码：

/**
    dp[i][j]表示从第i个人到第j个人这段区间的最小花费（是只考虑这j-i+1个人，不需要考虑前面有多少人）
    那么对于dp[i][j]的第i个人，就有可能第1个上场，也可以第j-i+1个上场。考虑第K个上场
    即在i+1之后的K-1个人是率先上场的，那么就出现了一个子问题 dp[i+1][i+k-1]表示在第i个人之前上场的
    对于第i个人，由于是第k个上场的，那么屌丝值便是a[i]*(k-1)
    其余的人是排在第k+1个之后出场的，也就是一个子问题dp[i+k][j]，对于这个区间的人，由于排在第k+1个之后，所以整体愤怒值要加上k*(sum[j]-sum[i+k-1])
    */
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int INF=0xffffff0;
    int dp[110][110];
    int w[110];
    int sum[110];
    int main()
    {
        
        int t,n;
        scanf("%d",&t);
        for(int cnt=1;cnt<=t;cnt++)
        {
        
            memset(dp,0,sizeof(dp));
            memset(sum,0,sizeof(sum));
            memset(w,0,sizeof(w));
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
            {
        
                for(int j=i+1;j<=n;j++)
                    dp[i][j]=INF;
            }
            for(int i=1;i<=n;i++)
            {
        
                scanf("%d",&w[i]);
                sum[i]=sum[i-1]+w[i];
            }
            for(int len=1;len<n;len++)
            {
        
                for(int i=1;i<=n-len;i++)
                {
        
                    int j=i+len;
                    for(int k=1;k<=j-i+1;k++)
                    {
        
                        dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+k*(sum[j]-sum[i+k-1])+w[i]*(k-1));
                    }
                }
            }
            printf("Case #%d: %d\n",cnt,dp[1][n]);
        }
    }

太难了！！！！（呜呜呜）

[五、hdu 4632：Palindrome subsequence][hdu 4632_Palindrome subsequence]

这感觉是一道简单题，还是太菜了，我觉得应该能做出来的，基本上找到区间dp的套路后，感觉这题套套路，应该还是能做出来啊

题意就是要求给定字符串的子序列为回文串的数量，由于数量巨大，于是得取模

思路：  
**用dp\[i\]\[j\]表示这一段里有多少个回文串，那首先dp\[i\]\[j\]=dp\[i+1\]\[j\]+dp\[i\]\[j-1\]，但是dp\[i+1\]\[j\]和dp\[i\]\[j-1\]可能有公共部分，所以要减去dp\[i+1\]\[j-1\]。  
如果str\[i\]==str\[j\]的话，还要加上dp\[i+1\]\[j-1\]+1，因为首尾是可以组成一个回文子串的，而且首尾可以与中间任何一个回文子串组成新的回文子串 。**

代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int mod=10007;
    char str[1010];
    int dp[1010][1010];
    int main()
    {
        
        int t;
        scanf("%d",&t);
        for(int k=1;k<=t;k++)
        {
        
            scanf("%s",str);
            int len=strlen(str);
            str[len]='\0';
            memset(dp,0,sizeof(dp));
            for(int i=0;i<len;i++)
                dp[i][i]=1;
            for(int j=1;j<len;j++)
            {
        
                for(int i=j-1;i>=0;i--)
                {
        
                    dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;
                    if(str[i]==str[j])
                        dp[i][j]=(dp[i][j]+dp[i+1][j-1]+1+mod)%mod;
                }
            }
            printf("Case %d: %d\n",k,dp[0][len-1]);
        }
        return 0;
    }

这应该还是能想到的啊…

[六、poj 1141：Brackets Sequence][poj 1141_Brackets Sequence]

又是括号匹配，感觉也不是很难，但是为什么就是没想到呢，

唯一有点想不到的就是那个打印的，其实用个递归也就游刃而解了

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    char str[1010];
    int dp[1010][1010];
    int pos[1010][1010];
    /**感觉就是这有点难*/
    void Print(int i,int j)
    {
        
        //递归结束条件
        if(i>j)
            return ;
        if(i==j)
        {
        
            if(str[i]=='('||str[j]==')')
                printf("()");
            else
                printf("[]");
        }
        else
        {
        
            if(pos[i][j]==-1)
            {
        
                printf("%c",str[i]);
                Print(i+1,j-1);
                printf("%c",str[j]);
            }
            else
            {
        
                Print(i,pos[i][j]);
                Print(pos[i][j]+1,j);
            }
        }
    }
    int main()
    {
        
        while(gets(str))
        {
        
            int len=strlen(str);
            str[len]='\0';
            memset(dp,0,sizeof(dp));
            memset(pos,0,sizeof(pos));
            for(int i=0;i<len;i++)
                dp[i][i]=1;
            //基本区间dp模板
            for(int l=1;l<len;l++)
            {
        
                for(int i=0;i<len-l;i++)
                {
        
                    int j=i+l;
                    dp[i][j]=0xffffff0;
                    if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
                    {
        
                        dp[i][j]=dp[i+1][j-1];
                        pos[i][j]=-1;
                    }
                    for(int k=i;k<j;k++)
                    {
        
                        int temp=dp[i][k]+dp[k+1][j];
                        if(dp[i][j]>temp)
                        {
        
                            dp[i][j]=temp;
                            pos[i][j]=k;
                        }
                    }
                }
            }
            Print(0,len-1);
            printf("\n");
        }
    }

[poj 3280_Cheapest Palindrome]: http://poj.org/problem?id=3280
[poj 2955_Brackets]: http://poj.org/problem?id=2955
[hdu 3506_Monkey Party]: http://acm.hdu.edu.cn/showproblem.php?pid=3506
[hdu 4283_You Are the One]: http://acm.hdu.edu.cn/showproblem.php?pid=4283
[hdu 4632_Palindrome subsequence]: http://acm.hdu.edu.cn/showproblem.php?pid=4632
[poj 1141_Brackets Sequence]: http://poj.org/problem?id=1141