acwing322消木块

本文主要是介绍acwing322消木块，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题目就当一个见识吧

设f[i][j][k]表示当前的状态是[i,j]并且j后面还有k个与j颜色相同的木块的最大价值

第一种情况，当第j块和第j-1块颜色相同时，f[i][j][k]=f[i][j-1][k+1]

第二种情况，当第j块和第j-1块颜色不同时，考虑最后那一堆颜色相同的怎么消去的

如果这一堆没有跟其他颜色相同的合并，那么对于任意一种操作，我们都可以把消去最后这一堆的子操作放在最开始，即最开始就消掉最后这一堆，而不影响答案，所以我们有$f[i][j][k]=f[i][j-1][0]+(1+k{)}^2$

如果我们要让最后这一堆跟前面的某一堆颜色相同的一起消去，我们不妨设最后第j块与原始序列的第p块挨在了一起

那么我们在消除第j块和第p块这连在一起的一堆之前的操作，一定是分开的，即在[1,p]和[p+1,j-1]这两个区间中间分别进行（因为不能增添木块只能消除），所以我们可以先全部进行[p+1,j-1]这个区间的操作在进行[1,p]这个区间的操作而不影响答案。而且根据以上分析，这个p一定是原始序列某一堆颜色相同的块中最右边的一块，而不会是中间的某一块，所以也就很好枚举了

具体见代码

#include<cstdio>
#include<algorithm>
#include<cstring> 
using namespace std;
const int N=210;
int f[N][N][N],a[N];
void dp(int i,int j,int k)
{if(f[i][j][k]) return;if(i==j) {f[i][j][k]=(1+k)*(1+k);return;}if(a[j]==a[j-1]){/*int l=j-1;while(a[l]==a[j]) l--;if(l==i-1) {f[i][j][k]=(j-i+1+k)*(j-i+1+k);return;}dp(i,l+1,k+j-l-1);f[i][j][k]=f[i][l+1][k+j-l-1];*/dp(i,j-1,k+1);f[i][j][k]=f[i][j-1][k+1];return;//注释的是另一种写法，两种没明显区别//但注释的写法确实要好一点，不用调用多次函数 }for(int l=j-1;l>=i;l--)if(a[l]==a[j]&&a[l+1]!=a[j]){dp(i,l,k+1),dp(l+1,j-1,0);f[i][j][k]=max(f[i][j][k],f[l+1][j-1][0]+f[i][l][1+k]);}dp(i,j-1,0);f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(1+k)*(1+k));
}
int main()
{int t,cnt=0;scanf("%d",&t);int n;while(t--){memset(f,0,sizeof(f));scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);dp(1,n,0);cnt++;printf("Case %d: %d\n",cnt,f[1][n][0]);}return 0;
}

洛谷的讨论区好像还有记忆化搜索的优化，可以看一下

这篇关于acwing322消木块的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---