这道题是我的第一百道紫题，当然要纪念一下啦。
首先这道题是一道区间DP，设\(f[i][j][k]\)表示在区间\([i,j]\)后，有连续的\(k\)个方块与第\(j\)个方块颜色相同的最大值；\(dis[i]\)表示在第\(i\)个块后面共有多少个与之颜色相同的块。
状态转移
1、把\([i,j-1]\)后的\((k+1)\)个方块一起消掉(第\(j\)个会被消掉)
方程为
\[f[i][j][k]=max\{f[i][j-1][0]+(k+1)^2\},0\le k\le dis[j]\]
2、在\([i,j-1]\)中选择一个块\(m\)满足\(a[j]=a[m]\)，那么就可以把区间\([m+1,j-1]\)消掉，状态转移方程为
\[f[i][j][k+1]=max\{f[i][m][0]+f[m+1][j][k]\},0\le k\le dis[j]\]
最后的答案为\(f[1][n][0]\)
上代码了
#include<bits/stdc++.h>
#define ll long long
#define N 205
#define M 200005
using namespace std;
int T,n,a[N],f[N][N][N],dis[N];
int main(){
scanf("%d",&T);
for(int Q=1;Q<=T;++Q){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
memset(f,0,sizeof f);memset(dis,0,sizeof dis);
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(a[i]==a[j])dis[i]++;
}
}
for(int i=n;i;--i){
for(int j=i;j<=n;++j){
for(int k=i;k<j;++k){
if(a[j]==a[k]){
for(int p=0;p<=dis[j];++p){
f[i][j][p]=max(f[i][j][p],f[k+1][j-1][0]+f[i][k][p+1]);
}
}
}
for(int k=0;k<=dis[j];++k){
f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(k+1)*(k+1));
}
}
}
printf("Case %d: %d\n",Q,f[1][n][0]);
}
return 0;
}