有n个带有颜色的方块，没消除一段长度为x的连续的相同颜色的方块可以得到x^2的分数，让你用一种最优的顺序消除所有方块使得得分最多。
输入格式 第一行包含测试的次数t（1≤t≤15） 每个案例包含两行。第一行包含整数n（1≤n≤200），即框数。第二行包含n个数，代表每个盒子的颜色。数字的大小1~n内。
Solution
n比较小，所以我们要用n^3的dp。
我们设dp[i][j][k]表示从i缩到j，j要和j后面的k个格子缩到一起能获得的最大分数。
转移的话枚举断点，如果有一个点和j相等，就把k向前传递，否侧向后传递。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int x,dp[][][],a[],b[],n,tot,t,p;
int dfs(int i,int j,int s){
if(dp[i][j][s])return dp[i][j][s];
if(i>j)return ;
if(i==j)return dp[i][j][s]=(b[j]+s)*(b[j]+s);
for(int k=i;k<j;++k)
if(a[k]==a[j])
dp[i][j][s]=max(dp[i][j][s],dfs(i,k,s+b[j])+dfs(k+,j-,));
else dp[i][j][s]=max(dp[i][j][s],dfs(i,k,)+dfs(k+,j,s));
return dp[i][j][s];
}
int main(){
cin>>t;
while(t--){
p++;
cin>>n;a[]=-;tot=;
memset(dp,,sizeof(dp));
for(int i=;i<=n;++i){
scanf("%d",&x);
if(x==a[tot])b[tot]++;
else a[++tot]=x,b[tot]=;
}
cout<<"Case "<<p<<": "<<dfs(,tot,)<<endl;
}
return ;
}