[关闭]
@Junlier 2018-09-21T20:36:15.000000Z 字数 1584 阅读 1837

Blocks题解

动态规划——区间dp

区间dp

可以去我的博客逛一逛的。。。eternal风度的博客
很好的一道区间dp的题目(别问我怎么想到的)

dp状态

其实这个题最难的地方是这道题目的状态怎么设

转移

:显然有两种转移
我这里是用记忆化搜索实现的

  1. 消掉j和后面的k块

    1. dp[i][j][k]=max(dp[i][j][k],Dfs(i,j-1,0)+(k+1)*(k+1));
  2. 对于区间,中间可能有和颜色相同的块,假设位置为,我们可以选择消掉区间中所有的块使颜色拼起来,当然这是个子问题,所以前面讲了用记忆化搜索实现
    PS: 下面代码的是预处理的在前面第一个和颜色相同的块的位置

    1. for(int p=nxt[j];p>=i;p=nxt[p])//枚举p
    2. dp[i][j][k]=max(dp[i][j][k],Dfs(i,p,k+1)+Dfs(p+1,j-1,0));

汇总

讲完这些整个程序的实现就不难了
那我直接放上代码,不好意思,没有注释

  1. #include<bits/stdc++.h>
  2. #define lst long long
  3. #define ldb double
  4. #define N 250
  5. using namespace std;
  6. const int Inf=1e9;
  7. int read()
  8. {
  9. int s=0,m=0;char ch=getchar();
  10. while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
  11. while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
  12. return m?-s:s;
  13. }
  14. int n;
  15. int col[N],nxt[N],hd[N];
  16. lst dp[N][N][N];//消掉[i,j]区间和[i,j]右边和j颜色一样的连续k个方块的最大分数
  17. lst Dfs(int i,int j,int k)
  18. {
  19. if(i>j)return 0;
  20. if(dp[i][j][k])return dp[i][j][k];
  21. dp[i][j][k]=max(dp[i][j][k],Dfs(i,j-1,0)+(k+1)*(k+1));
  22. for(int p=nxt[j];p>=i;p=nxt[p])
  23. dp[i][j][k]=max(dp[i][j][k],Dfs(i,p,k+1)+Dfs(p+1,j-1,0));
  24. return dp[i][j][k];
  25. }
  26. int main()
  27. {
  28. int T=read();
  29. for(int tt=1;tt<=T;++tt)
  30. {
  31. n=read();
  32. memset(hd,0,sizeof(hd));
  33. memset(dp,0,sizeof(dp));
  34. memset(nxt,0,sizeof(nxt));
  35. for(int i=1;i<=n;++i)
  36. {
  37. col[i]=read();
  38. nxt[i]=hd[col[i]];
  39. hd[col[i]]=i;
  40. }
  41. printf("Case %d: %lld\n",tt,Dfs(1,n,0));
  42. }
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注