题目链接: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]jka[j]dp[i][j][k]=dp[i][j1][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,j1]a[j]a[r]dp[i][j][k]=dp[i][r][b[j]+k]+dp[r+1][j1][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;
}