题目：https://www.luogu.org/problemnew/show/UVA10559
应该想到区间dp。但怎么设计状态？
因为连续的东西有分值，所以应该记录一下连续的有多少个。
只要记录与边界连续的有多少个就能涵盖所有的连续了。只记一边的边界即可。
两个转移：用掉记录的那些连续的 或 在自己区间中再找一个一样颜色的使连续数量+1。
用掉了以后剩余部分的连续长度就是0。也许 j-1 和 j 同色，但这个可以在另一个转移里体现，所以没问题。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int T,n,a[N],dp[N][N][N];
int rdn()
{
int ret=,fx=; char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=-; ch=getchar();}
while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return ret*fx;
}
void init()
{
memset(dp,,sizeof dp);
}
int main()
{
T=rdn();
for(int t=;t<=T;t++)
{
init();
n=rdn(); for(int i=;i<=n;i++) a[i]=rdn();
for(int i=;i<=n;i++)
for(int k=;k<=(n-i);k++)
dp[i][i][k]=(k+)*(k+);
for(int d=,lm=n-d+;d<=n;d++)
for(int i=,j,LM;i<=lm;i++)
{
j=i+d-; LM=n-j;
for(int k=;k<=LM;k++)
{
dp[i][j][k]=dp[i][j-][]+(k+)*(k+);
for(int l=i;l<j;l++)
if(a[l]==a[j])
dp[i][j][k]=max(dp[i][j][k],
dp[i][l][k+]+dp[l+][j-][]);
//printf("dp[%d][%d][%d]=%d\n",i,j,k,dp[i][j][k]);
}
}
printf("Case %d: %d\n",t,dp[][n][]);
}
return ;
}