题目：https://www.luogu.org/problemnew/show/UVA10559
区间DP，有点难想；
为了方便，先把原来就是连续一段相同颜色的点看做一个点，记一下长度；
f[i][j][k] 表示右边有 k 个和 j 颜色相同的点时(其它都已经各自被消掉)，消除 i ~ j 区间的答案；
从消除 j 点来考虑，有两种方法：1.和右边那 k 个点合并消除，所以 f[i][j][k] = f[i][j-1][0] + ( len[j] + k )2
2.和右边以及区间中的某个相同颜色的点一起合并消除，所以 f[i][j][k] = max{ f[i][p][k+len[j]] + f[p+1][j-1][0] } ，col[p] = col[j]
虽然只考虑了右边，但左边会在之后算左边的区间时被算上，所以可以覆盖所有情况；
(不太会赋的)初值是 f[i][i][0] = len[i]2 ，f[i][i-1][0]=0 (进入 i,i,k 时会被枚举到 )；
其实不太会DP的顺序，写了个长度从小到大的却错了(大概是初值不一样吧，但是不太会)，干脆变成记忆化搜索。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=;
int T,n,a[maxn],col[maxn],len[maxn],f[maxn][maxn][maxn],s[maxn],lst[maxn];
int sqr(int x){return x*x;}
int dp(int l,int r,int k)
{
if(f[l][r][k]!=-)return f[l][r][k];
f[l][r][k]=dp(l,r-,)+sqr(len[r]+k);
for(int p=l;p<r;p++)
if(col[p]==col[r])
f[l][r][k]=max(f[l][r][k],dp(l,p,k+len[r])+dp(p+,r-,));
return f[l][r][k];
}
int main()
{
scanf("%d",&T); int tt=;
while(T--)
{
tt++;
// memset(lst,0,sizeof lst);
memset(len,,sizeof len);
memset(f,-,sizeof f);
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
int cnt=;
for(int i=,nw;i<=n;i=nw+)
{
nw=i; col[++cnt]=a[nw]; len[cnt]=;//
while(a[nw]==a[nw+])nw++,len[cnt]++;
}
// for(int i=n;i;i--)
// {
// s[i]=lst[col[i]]+1;
// lst[col[i]]++;
// }
n=cnt;
for(int i=;i<=n;i++)f[i][i][]=sqr(len[i]),f[i][i-][]=;//!
// for(int l=2;l<=n;l++)
// for(int i=1;i<=n;i++)
// {
// int j=i+l;
// for(int k=0;k<=s[j]-1;k++)
// {
// f[i][j][k]=f[i][j-1][0]+sqr(len[j]+k);
// for(int p=i;p<j;p++)//<
// if(col[p]==col[j])
// f[i][j][k]=max(f[i][j][k],f[i][p][k+len[j]]+f[p+1][j-1][0]);//k+1
// }
// }
printf("Case %d: %d\n",tt,dp(,n,));
}
return ;
}