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}=\max\limits_{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\n" ,o,dp[1][n][0]);
    }
    return 0;
}