UVA10559 Blocks

题目
设(f_{i,j,k})表示消掉([i,j])区间，且(j)右边还有(k)个和(j)同色的方块的分数。
转移分为两种：
(1.)将(j)右边(k)个与(j)同色的方块一起消掉，(f_{i,j,k}=f_{i,j-1,0}+(k+1)^2)
(2.)在([i,j))中任找一个和(j)颜色相同的方块(l)，将((l,j))消掉使得(l,j)相邻，(f_{i,j,k}=maxlimits_{col_l=col_j}(f_{l+1,j-1,0}+f_{i,l,k+1}))
在常数为几分之一的情况下(O(n^4))过(200)还是绰绰有余的。

#include<bits/stdc++.h>
using namespace std;
const int N=201;
int a[N],dp[N][N][N],sum[N];
inline int read()
{
    register int a=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        a=(a<<3)+(a<<1)+(ch^'0'),ch=getchar();
    return a;
}
inline int max(int a,int b)
{
	return a>b? a:b;
}
int main()
{
	register int T=read();
	for(register int o=1;o<=T;++o)
	{
		register int n=read();
		memset(dp,0,sizeof(dp));
		memset(sum,0,sizeof(sum));
		for(register int i=1;i<=n;++i)
			a[i]=read();
		for(register int i=n-1;i;--i)
            for(register int j=i+1;j<=n;++j)
                if(a[i] == a[j])
                    sum[i]++;
        for(register int i=n;i;--i)
            for(register int j=i;j<=n;++j)
			{
                for(register int p=i;p<j;++p)
                    if(a[p]==a[j])
                        for(register int k=0;k<=sum[j];++k)
                            dp[i][j][k]=max(dp[i][j][k],dp[p+1][j-1][0]+dp[i][p][k+1]);
                for(register int k=0;k<=sum[j];++k)
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][0]+(k+1)*(k+1));
            }
        printf("Case %d: %d
" ,o,dp[1][n][0]);
	}
	return 0;
}