思路：
黑书的例题
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #define Maxn 210 using namespace std; int dp[Maxn][Maxn][Maxn],col[Maxn],len[Maxn],pre[Maxn],aper[Maxn],after[Maxn],vi[Maxn]; int main() { int t,n,i,j,x,k,Case=0; int cnt=0; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); memset(len,0,sizeof(len)); memset(aper,0,sizeof(aper)); cnt=0; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&x); if(x!=col[cnt]) col[++cnt]=x,len[cnt]=1,pre[cnt]=aper[x],aper[x]=cnt; else len[cnt]++; } memset(vi,0,sizeof(vi)); for(i = cnt; i >= 1; i--){ if(vi[i]) continue; after[i] = 0; int tmp = i; for(j = i-1; j >= 1; j--) if(col[j] == col[tmp]){ after[j] = after[tmp] + len[tmp]; tmp = j; vi[j--] = true; } } int l; for(l=0;l<=cnt;l++){ for(i=1;i+l<=cnt;i++){ j=i+l; for(k=0;k<=after[j];k++){ dp[i][j][k]=dp[i][j-1][0]+(len[j]+k)*(len[j]+k); int p=pre[j]; while(p>=i){ dp[i][j][k]=max(dp[i][j][k], dp[i][p][k+len[j]]+dp[p+1][j-1][0]); p=pre[p]; } } } } printf("Case %d: %d ",++Case,dp[1][cnt][0]); } return 0; }