[关闭]
@suixinhita 2017-10-10T00:29:45.000000Z 字数 4005 阅读 1193

区间DP

区间DP是个好东西(。)水了几道题。
一般说来,区间DP是一个很容易想到的地方,方程也非常好设置,一般是这样的:


其中, , 分别表示左右端点, 一般用来表示另外一个状态量(有 存在时,多选用递归求解。)
对于一般的没有 的区间DP来说,我们选择递推解决,会比较方便。

递推套路(???)如下:

  1. for(int l=2;l<=n;++l)
  2. for(int i=1;i+l<=n;++i)
  3. {
  4. int j=i+l;
  5. for(int k=i;k<=j;++k)
  6. dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j]);
  7. }

需要注意的几个点

1.区间长度从 开始, 是留给初始化的。
2. 是严格小于 的。
3.个别题目可以使用平行四边形优化。

所以还是扯一下平行四边形优化。
准确的说,平行四边形优化就是在转移的时候,把转移的状态记录下来了。
也就是,记忆化了每一个
这样的话,我们在枚举 的时候就会有了一个很小的区间。
通常来说是

这样可以优化掉一层复杂度。
但是不幸的是,不是每一个区DP都可以这样优化的。
数学分析对于这个优化是比较难的,所以我们可以直接打表寻找是否可以使用。
打表之后,如果每一行或者每一列都是单调的,就可以放心平行四边形优化了。

比如这样:

  1. for(int l=2;l<=n;++l)
  2. {
  3. for(int i=1;i+l-1<=n;++i)
  4. {
  5. int j=i+l-1;
  6. dp[i][j]=inf;
  7. for(int k=s[i][j-1];k<=s[i+1][j];++k)//首先说一下这里是i j-1到
  8. //i+1 j 后面这个注意
  9. {
  10. if(dp[i][j]>dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1])
  11. //k+1 i-1注意
  12. {
  13. dp[i][j]=dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1];
  14. s[i][j]=k;
  15. }
  16. }
  17. }
  18. }

就是这样的了~

再说一下对于状态的转移(一般说来情况并不多):

1.对于大部分裸一点的DP问题,可以很明确的知道合并区间所需代价。
2.对于区间合并后会出现两个区间合并的代价未知的情况,比如括号的合并,就需要把很多状态抽象成一种,大多数时候是一定一动的抽象(这个比较...)稍后再分析。
3.对于状态转移多到要 狗带 的那些个状态,我们选择记忆化搜索。

那么现在就来说对于区间合并后的代价要判断的题目。

poj2955 括号匹配

题目意思很简单,就是给你一堆括号,问你这一堆里面,有多少个是匹配了的。

这个就需要我们抽象一下,因为在区间里面的没匹配的括号对于区间合并是非常不友好的,所以我们希望把这些去掉。
那么我们思考,对于两个区间里面的括号的匹配,其实我们都可以看做是另外两个每一个都自己匹配好了的区间 这么绕口?? 比如这样:

[ [ ( ( ] 和 ) ) ] == [ [ ( ( ] ) ) 和 ]

由此可以知道,对于区间合并,我们都可以抽象成两个区间两端的合并,因为剩下的在里面的会在枚举区间断点的时候枚举到,所以不会有状态没有枚举的情况。

  1. /*
  2. 括号匹配。
  3. 把所有区间合并分为两个子问题。
  4. 第一种是直接合并 eg. (()) && {{}}[]
  5. 第二种是包含性合并 eg. (() && {{[]}})
  6. */
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<algorithm>
  10. using namespace std;
  11. const int N=155;
  12. const int inf=0x3f3f3f3f;
  13. int dp[N][N];
  14. char s[N];
  15. bool check(char x,char y)
  16. {
  17. if(x=='('&&y==')') return 1;
  18. if(x=='['&&y==']') return 1;
  19. return 0;
  20. }
  21. bool solve()
  22. {
  23. scanf("%s",s+1);
  24. int n=strlen(s+1);
  25. if(s[1]=='e') return 0;
  26. memset(dp,0,sizeof(dp));
  27. for(int l=2;l<=n;++l)
  28. {
  29. for(int i=1;i+l-1<=n;++i)
  30. {
  31. int j=i+l-1;
  32. if(check(s[i],s[j]))
  33. dp[i][j]=dp[i+1][j-1]+2;
  34. for(int k=i;k<j;++k)
  35. dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
  36. }
  37. }
  38. printf("%d\n",dp[1][n]);
  39. return 1;
  40. }
  41. int main()
  42. {
  43. while(solve());
  44. return 0;
  45. }

然后我们来说需要用到记忆化搜索的 神题
首先,这两道题非常相似,都是涉及了字符串的压缩。
所以对比一下

bzoj1068 & bzoj1090

1068

这道题的话,是把字符串的压缩,简化成了前后两半字符串的相等。因为这道题每次的压缩是不相等并且可以共有一个开头的。

1090

这道题是把字符串的压缩,变成了前后串判断是否可以压缩,也就是,后边的串是不是由前面的重复几遍得来的。

但是这两道题的DP方程是非常不一样的,1068的dp方程使用了前文提到的 因为他可以共有开头 ,但1090不同,不需要 ,因为不能与前面一起用一个开头。

并且,对于为什么要选择对于1068判断的时候要用到剖成两半的方式,我想,还是因为这个题中,状态转移有很多种:

  1. 时,
    我们枚举区间中插 的地方。那么前后我们就有四种可能性。

  2. 时,
    分为很多种情况,

    1. 后面可以压缩,因为我们假设每一个区间前面( 处,都有一个
      2.后面不能压缩,所以我们直接加上后面的长度。
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N=55;
  6. const int inf=0x3f3f3f3f;
  7. int dp[N][N][2],n;
  8. char s[N];
  9. bool check(int l,int r)
  10. {
  11. if((r-l+1)&1) return 0;
  12. int mid=l+r>>1;
  13. for(int i=l;i<=mid;++i)
  14. if(s[i]!=s[mid+i-l+1]) return 0;
  15. return 1;
  16. }
  17. int solve(int l,int r,int k)
  18. {
  19. if(dp[l][r][k]<inf) return dp[l][r][k];
  20. int len=r-l+1;
  21. if(len==1)
  22. {
  23. if(k) return dp[l][r][k]=inf;
  24. else return dp[l][r][k]=1;
  25. }
  26. else
  27. {
  28. if(k)
  29. {
  30. for(int i=l;i<r;++i)
  31. {
  32. dp[l][r][k]=min(dp[l][r][k],solve(l,i,1)+1+solve(i+1,r,1));
  33. dp[l][r][k]=min(dp[l][r][k],solve(l,i,1)+1+solve(i+1,r,0));
  34. dp[l][r][k]=min(dp[l][r][k],solve(l,i,0)+1+solve(i+1,r,1));
  35. dp[l][r][k]=min(dp[l][r][k],solve(l,i,0)+1+solve(i+1,r,0));
  36. }
  37. return dp[l][r][k];
  38. }
  39. }
  40. int mid=l+r>>1;
  41. if(check(l,r)) dp[l][r][k]=solve(l,mid,0)+1;
  42. for(int i=l;i<r;++i)
  43. dp[l][r][k]=min(dp[l][r][k],solve(l,i,0)+r-i);
  44. return dp[l][r][k];
  45. }
  46. int main()
  47. {
  48. memset(dp,inf,sizeof(dp));
  49. scanf("%s",s+1);
  50. n=strlen(s+1);
  51. printf("%d\n",min(solve(1,n,0),solve(1,n,1)));
  52. return 0;
  53. }

然后对于1090来说,我们就可以省略有没有 的步骤,因为有没有这个,没关系的。
所以说我们直接暴力匹配前面和后面的串是不是循环,是了合并,不是直接加,简单粗暴(另外还有hash方式暴力匹配,不多说了。)

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N=105;
  6. const int inf=0x3f3f3f3f;
  7. int dp[N][N],n;
  8. char s[N];
  9. int size(int len,int L)
  10. {
  11. if(L/len<10) return 1;
  12. if(L/len<100) return 2;
  13. return 3;
  14. }
  15. bool check(int l,int r,int l2,int r2)
  16. {
  17. int L=r-l+1,LL=r2-l2+1;
  18. if(L%LL!=0) return 0;
  19. for(int i=l;i<=r;++i)
  20. {
  21. int j=(i-l)%LL+l2;
  22. if(s[i]!=s[j]) return 0;
  23. }
  24. return 1;
  25. }
  26. int solve(int l,int r)
  27. {
  28. if(l==r) return 1;
  29. if(dp[l][r]!=inf) return dp[l][r];
  30. int len=r-l+1;
  31. for(int i=l;i<r;++i)
  32. {
  33. len=min(len,solve(l,i)+solve(i+1,r));
  34. if(check(i+1,r,l,i))
  35. len=min(len,solve(l,i)+2+size((i-l+1),(r-l+1)));
  36. }
  37. return dp[l][r]=len;
  38. }
  39. int main()
  40. {
  41. scanf("%s",s+1);
  42. n=strlen(s+1);
  43. memset(dp,inf,sizeof(dp));
  44. printf("%d",solve(1,n));
  45. return 0;
  46. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注