题目大意：给你玩一个一维版的消灭星星，得分是当前消去的区间的长度的平方，求最大得分。
现在分析一下题目
因为得分是长度的平方，不能直接累加，所以在计算得分时需要考虑前一个状态所消去的长度，仅用dp[l][r]来表示区间最大得分是不足以用来转移的。
我们的解决方法是：增加一维预测未来可能会出现的情况，用dp[l][r][t]表示区间[l,r]之后附加t个与r同色的方块时所能得到的最大值。为了降低时间复杂度，我们可以在读入时处理一下，将一段长度为a、颜色为b的区间k表示成一个len[k]=a,col[k]=b的“点”。这样，当我们计算dp[l][r][0]时，首先尝试直接消除区间r，得到dp[l][r][0]=dp[l][r-1][0]+(len[r])^2，接着，将它之后所有可能的附加t个同色方块的情况都算出来：dp[l][r][t]=dp[l][r-1][0]+(len[r]+t)^2。之后，在[l,r-1]之间寻找可能与区间r同色的区间k，若col[r]==col[k]，则尝试消除区间r与k之间的所有方块，让区间r与k并在一起计算分数并更新所有dp[l][r][t]的值：dp[l][r][t]=max(dp[l][r][t],dp[l][k][len[r]+t]+dp[k+1][r-1][0])。最后dp[1][n][0]即为答案。（n为一开始同色区间的数量）
代码：（140ms,用递推速度就是不一样，比记搜不知道高到哪里去了）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int col[],len[],dp[][][];
int sum[];
//by sclbgw7
inline int sq(int x)
{return x*x;} inline int maxn(int x,int y)
{return x>y?x:y;} int main()
{
int T,time;
scanf("%d",&T);
for(time=;time<=T;++time)
{
int n=,m,t1;//m为方块个数，n为区间个数
scanf("%d",&m);
for(int i=;i<=m;++i)
{
scanf("%d",&t1);
if(t1==col[n])
++len[n];
else
{
col[++n]=t1;
len[n]=;
}
}
for(int i=;i<=n;++i)
sum[i]=sum[i-]+len[i];//sum为前缀和，用于限定预测t的范围
memset(dp,,sizeof(dp));
for(int i=;i<n;++i)
for(int l=;l+i<=n;++l)
{
int r=l+i,re=sum[n]-sum[r];//re为当前t可能用到的最大值
for(int t=;t<=re;++t)
dp[l][r][t]=dp[l][r-][]+sq(t+len[r]);
for(int k=r-;k>=l;--k)
if(col[k]==col[r])
for(int t=;t<=re;++t)
dp[l][r][t]=maxn(dp[l][r][t],dp[l][k][len[r]+t]+dp[k+][r-][]);
}
printf("Case %d: %d\n",time,dp[][n][]);
//神坑！！！！！冒号之后要加一个空格！！！！！！！
}
return ;
}