这个题目就当一个见识吧
设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;
}