题目链接：http://poj.org/problem?id=1390&tdsourcetag=s_pctim_aiomsg
题目大意：一个积木游戏，有连续的n个方块。相同颜色的方块连续方块可以消除。如果该段由k个积木组成。得分为k*k。

<mstyle displaystyle="false" scriptlevel="0"> 我 们 首 先 把 相 同 颜 色 的 积 木 合 并 成 一 个 块 a [ i ] , 用 b [ i ] 表 示 a [ i ] 有 多 少 个 积 木 。 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> 我 们 用 d p [ i ] [ j ] [ k ] : 表 示 段 [ i , j ] 并 且 j 的 右 边 有 k 个 和 a [ j ] 颜 色 相 同 的 积 木 能 获 得 的 最 大 得 分 。 </mstyle> <mstyle displaystyle="false" scriptlevel="0"> </mstyle> <mstyle displaystyle="false" scriptlevel="0"> 考 虑 转 移 ： d p [ i ] [ j ] [ k ] = d p [ i ] [ j − 1 ] [ 0 ] + ( b [ j ] + k ) ∗ ( b [ j ] + k ) </mstyle> \begin{array}{l} 我们首先把相同颜色的积木合并成一个块a[i],用b[i]表示a[i]有多少个积木。\\\\ 我们用dp[i][j][k]:表示段[i,j]并且j的右边有k个和a[j]颜色相同的积木能获得的最大得分。\\\\ 考虑转移：dp[i][j][k]=dp[i][j-1][0]+(b[j]+k)*(b[j]+k) \end{array} 我们首先把相同颜色的积木合并成一个块a[i],用b[i]表示a[i]有多少个积木。我们用dp[i][j][k]:表示段[i,j]并且j的右边有k个和a[j]颜色相同的积木能获得的最大得分。考虑转移：dp[i][j][k]=dp[i][j−1][0]+(b[j]+k)∗(b[j]+k)​

还 有 一 种 转 移 ， 在 [ i , j − 1 ] 种 如 果 有 和 a [ j ] 颜 色 相 同 的 块 a [ r ] ： d p [ i ] [ j ] [ k ] = d p [ i ] [ r ] [ b [ j ] + k ] + d p [ r + 1 ] [ j − 1 ] [ 0 ] 还有一种转移，在[i, j-1]种如果有和a[j]颜色相同的块a[r]：\\\\ dp[i][j][k]=dp[i][r][b[j]+k]+dp[r+1][j-1][0] 还有一种转移，在[i,j−1]种如果有和a[j]颜色相同的块a[r]：dp[i][j][k]=dp[i][r][b[j]+k]+dp[r+1][j−1][0]

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int a[205], b[205], len[205], f[205][205][205];

int DP(int l, int r, int k){
    if(r<l) return 0;
    if(f[l][r][k]!=-1) return f[l][r][k];
    int ans=DP(l, r-1, 0)+(len[r]+k)*(len[r]+k);
    for(int i=l; i<r; i++){
        if(a[i]==a[r]){
            ans=max(ans, DP(l, i, len[r]+k)+DP(i+1, r-1, 0));
        }
    }
    return f[l][r][k]=ans;
}

int main() {

    int t, T=1; scanf("%d", &t);
    while(t--){
        memset(f, -1, sizeof(f));
        memset(len, 0, sizeof(len));
        int n; scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%d", &b[i]);
        }
        int tot=1;
        a[tot]=b[1], len[1]=1;
        for(int i=2; i<=n; i++){
            if(b[i]!=b[i-1]){
                a[++tot]=b[i]; len[tot]=1;
            }
            else{
                len[tot]++;
            }
        }

        printf("Case %d: %d\n", T++, DP(1, tot, 0));
    }

    return 0;
}