devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

区间dp模型

作者：笔触狂放9 | 2024-05-03 21:16:19

赞

踩

区间dp模型

区间dp顾名思义就是在一个区间上进行的一系列动态规划。对一些经典的区间dp总结在这里。


1) 石子归并问题


题目链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=737


描述： 有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。


分析：要求n个石子归并，我们根据dp的思想划分成子问题，先求出每两个合并的最小代价，然后每三个的最小代价，依次知道n个。

定义状态dp [ i ] [ j ]为从第i个石子到第j个石子的合并最小代价。

那么dp [ i ] [ j ] = min(dp [ i ] [ k ] + dp [ k+1 ] [ j ]) 

那么我们就可以从小到大依次枚举让石子合并，直到所有的石子都合并。

这个问题可以用到平行四边形优化，用一个s【i】【j】=k 表示区间 i---j 从k点分开才是最优的，这样的话我们就可以优化掉一层复杂度，变为O（n^2）.

代码：

[cpp]  view plain  copy
 print ?
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <algorithm>  
  4. #define N 210  
  5. int dp[N][N],sum[N];  
  6. int main()  
  7. {  
  8.     int n;  
  9.     while(~scanf("%d",&n))  
  10.     {  
  11.         int a[N];sum[0]=0;  
  12.         for(int i=1;i<=n;i++){  
  13.             scanf("%d",&a[i]);  
  14.             sum[i]=sum[i-1]+a[i];  
  15.         }  
  16.         memset(dp,0,sizeof(dp));  
  17.         int i,j,l,k;  
  18.         for(l = 2; l <= n; ++l)  
  19.         {  
  20.             for(i = 1; i <= n - l + 1; ++i)  
  21.             {  
  22.                 j = i + l - 1;  
  23.                 dp[i][j] = 2100000000;  
  24.                 for(k = i; k < j; ++k)  
  25.                 {  
  26.                     dp[i][j] = std::min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1]);  
  27.                 }  
  28.             }  
  29.         }  
  30.         printf("%d\n", dp[1][n]);  
  31.     }  
  32.     return 0;  
  33. }  

平行四边形优化代码：

[cpp]  view plain  copy
 print ?
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <algorithm>  
  4. #define N 210  
  5. int dp[N][N],sum[N],s[N][N];  
  6. int main()  
  7. {  
  8.     int n;  
  9.     while(~scanf("%d",&n))  
  10.     {  
  11.         int a[N];sum[0]=0;  
  12.         memset(s,0,sizeof(s));  
  13.         for(int i=1;i<=n;i++){  
  14.             scanf("%d",&a[i]);  
  15.             s[i][i]=i;  
  16.             sum[i]=sum[i-1]+a[i];  
  17.         }  
  18.         memset(dp,0,sizeof(dp));  
  19.         int i,j,l,k;  
  20.         for(l = 2; l <= n; ++l)  
  21.         {  
  22.             for(i = 1; i <= n - l + 1; ++i)  
  23.             {  
  24.                 j = i + l - 1;  
  25.                 dp[i][j] = 2100000000;  
  26.                 for(k = s[i][j-1]; k <= s[i+1][j]; ++k)  
  27.                 {  
  28.                     if(dp[i][j]>dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1])  
  29.                     {  
  30.                         dp[i][j]=dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1];  
  31.                         s[i][j]=k;  
  32.                     }  
  33.                 }  
  34.             }  
  35.         }  
  36.         printf("%d\n", dp[1][n]);  
  37.     }  
  38.     return 0;  
  39. }  



2)括号匹配


题目链接：

poj2955,http://poj.org/problem?id=2955

nyoj 15 http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=15


描述：给出一串的只有‘（’ ‘）’  '[‘  ']'四种括号组成的串，让你求解需要最少添加括号数让串中的所有括号完全匹配。


分析：我们求出这个串的最大匹配，然后串的总长度-最大匹配就是答案。


方法1:首先能想到的是转化成LCS（最长公共子序列），枚举中间点，求所有的LCS中的最大值 * 2就是最大匹配。但是复杂度较高，光LCS一次就O(n^2)的复杂度。


方法2：

首先考虑怎么样定义dp让它满足具有通过子结构来求解、

定义dp [ i ] [ j ] 为串中第 i 个到第 j 个括号的最大匹配数目

那么我们假如知道了 i 到 j 区间的最大匹配，那么i+1到 j+1区间的是不是就可以很简单的得到。

那么 假如第 i 个和第 j 个是一对匹配的括号那么dp [ i ] [ j ] = dp [ i+1 ] [ j-1 ] + 2 ;

那么我们只需要从小到大枚举所有 i 和 j 中间的括号数目，然后满足匹配就用上面式子dp，然后每次更新dp [ i ] [ j ]为最大值即可。

更新最大值的方法是枚举 i 和 j 的中间值，然后让 dp[ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i ] [ f ] + dp [ f+1 ] [ j ] ) ;


如果要求打印路径，即输出匹配后的括号。见http://blog.csdn.net/y990041769/article/details/24238547详细讲解

代码：

[cpp]  view plain  copy
 print ?
  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <algorithm>  
  4. #include <string>  
  5. using namespace std;  
  6. const int  N = 120;  
  7. int dp[N][N];  
  8. int main()  
  9. {  
  10.     string s;  
  11.     while(cin>>s)  
  12.     {  
  13.         if(s=="end")  
  14.             break;  
  15.         memset(dp,0,sizeof(dp));  
  16.         for(int i=1;i<s.size();i++)  
  17.         {  
  18.             for(int j=0,k=i;k<s.size();j++,k++)  
  19.             {  
  20.                 if(s[j]=='('&&s[k]==')' || s[j]=='['&&s[k]==']')  
  21.                     dp[j][k]=dp[j+1][k-1]+2;  
  22.                 for(int f=j;f<k;f++)  
  23.                     dp[j][k]=max(dp[j][k],dp[j][f]+dp[f+1][k]);  
  24.             }  
  25.         }  
  26.         cout<<dp[0][s.size()-1]<<endl;  
  27.     }  
  28.     return 0;  
  29. }  


3 )题目链接：Brackets Sequence


题目描述：给出一串由‘（‘）’‘ [ ' ' ] '组成的串，让你输出添加最少括号之后使得括号匹配的串。


分析：是区间dp的经典模型括号匹配。讲解：http://blog.csdn.net/y990041769/article/details/24194605 ，难点在于要把匹配后的括号输出来。


首先我们知道前面定义dp [ i ] [ j ] 为串中第 i 个到第 j 个括号的最大匹配数目


那么假如我们知道任意 i 到 j 从哪儿插入分点使得匹配添加括号最少。那么我们定义pos【i】【j】表示 i 到 j 从哪儿分开使得匹配添加括号最少，如果i和j匹配我们可以让pos【i】【j】=-1；


我们发现在我们之前更新dp [ i ] [ j ] 的时候如果中间点k使得if ( dp [ i ] [ k ] + dp [ k+1 ] [ j ] >= dp [ i ] [ j ] ) ，那么我们从k分开可以让添加的括号最少。


但是还要注意一点，考虑所有的都不匹配如“((((”这类，考虑怎么处理，然后就可以递归输出结果。


这题目坑了我很多次，刚开始Tel，发现全部不匹配不能处理，改了之后wa了。发现输入“（）（（）”，输出的是“（（）（）（））”，明显错误，是在处理的时候没处理好，最后注意输入会有空串。

代码：

[cpp]  view plain  copy
 print ?
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <algorithm>  
  4. #include <cstring>  
  5. using namespace std;  
  6. const int  N = 120;  
  7. int dp[N][N],pos[N][N];   ///i到j从哪个位置分开添加的括号数最少  
  8. char s[N];  
  9. void show(int i,int j)  
  10. {  
  11.     if(i>j)  return;  
  12.     if(i==j)  
  13.     {  
  14.         if(s[i]=='('||s[i]==')') cout<<"()";  
  15.         else      cout<<"[]";  
  16.     }  
  17.     else  
  18.     {  
  19.         if(pos[i][j]==-1)  
  20.         {  
  21.             cout<<s[i];  
  22.             show(i+1,j-1);  
  23.             cout<<s[j];  
  24.         }  
  25.         else  
  26.         {  
  27.             show(i,pos[i][j]);  
  28.             show(pos[i][j]+1,j);  
  29.         }  
  30.     }  
  31. }  
  32. int main()  
  33. {  
  34.     while(gets(s))  
  35.     {  
  36.         memset(dp,0,sizeof(dp));  
  37.         int len=strlen(s);  
  38.         for(int i=1; i<len; i++)  
  39.         {  
  40.             for(int j=0,k=i; k<len; j++,k++)  
  41.             {  
  42.                 if(s[j]=='('&&s[k]==')' || s[j]=='['&&s[k]==']')  
  43.                 {  
  44.                     dp[j][k]=dp[j+1][k-1]+2;  
  45.                     pos[j][k]=-1;  
  46.                 }  
  47.                 for(int f=j; f<k; f++)  
  48.                 {  
  49.                     if(dp[j][f]+dp[f+1][k]>=dp[j][k])  ///注意这里 保证所有都不匹配也能够分  
  50.                     {  
  51.                         dp[j][k]=dp[j][f]+dp[f+1][k];  
  52.                         pos[j][k]=f;  
  53.                     }  
  54.                 }  
  55.             }  
  56.         }  
  57.         //cout<<s.size()-dp[0][s.size()-1]<<endl;  
  58.         show(0,len-1);cout<<endl;  
  59.     }  
  60.     return 0;  
  61. }  



4）整数划分问题


题目链接：nyoj746 http://acm.nyist.net/JudgeOnline/problem.php?pid=746


题目描述：给出两个整数 n , m ,要求在 n 中加入m - 1 个乘号，将n分成m段，求出这m段的最大乘积


分析：根据区间dp的思想，我们定义dp [ i ] [ j ]为从开始到 i 中加入 j 个乘号得到的最大值。

那么我们可以依次计算加入1----m-1个乘号的结果

而每次放入x个乘号的最大值只需枚举第x个乘号的放的位置即可

dp [ i ] [ j ]  = MAX (dp [ i ] [ j ] , dp [ k ] [ j-1 ] * a [ k+1 ] [ i ] ) ;


代码：

[cpp]  view plain  copy
 print ?
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #define MAX(a,b) a>b?a:b  
  4. long long a[20][20];  
  5. long long dp[25][25];  
  6. int main()  
  7. {  
  8.     int T,m;  
  9.     scanf("%d",&T);  
  10.     getchar();  
  11.     while(T--)  
  12.     {  
  13.         char s[22];  
  14.         scanf("%s",s+1);  
  15.         scanf("%d",&m);  
  16.         int l=strlen(s),ok=1;  
  17.         memset(a,0,sizeof(a));  
  18.         for(int i=1;i<l;i++)  
  19.         {  
  20.             if(s[i]=='0')  
  21.                 ok=0;  
  22.             for(int j=i;j<l;j++)  
  23.             {  
  24.                 a[i][j]=a[i][j-1]*10+(s[j]-'0');  
  25.             }  
  26.         }  
  27.         if(ok==0&&l-1==m||l-1<m)  
  28.         {  
  29.             printf("0\n");continue;  
  30.         }  
  31.         long long x,ans;  
  32.         memset(dp,0,sizeof(dp));  
  33.         for(int i=0;i<l;i++)  
  34.             dp[i][1]=a[1][i];  
  35.         ans=0;  
  36.         if(m==1)  
  37.             ans=dp[l-1][1];  
  38.         for(int j=2;j<=m;j++)  
  39.         {  
  40.             for(int i=j;i<l;i++)  
  41.             {  
  42.                 ans=a[i][i];  
  43.                 for(int k=1;k<i;k++)  
  44.                 {  
  45.                     dp[i][j]=MAX(dp[i][j],dp[k][j-1]*a[k+1][i]);  
  46.                 }  
  47.             }  
  48.         }  
  49.         printf("%lld\n",dp[l-1][m]);  
  50.     }  
  51.     return 0;  
  52. }  
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/531560
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号