…
http://poj.org/problem?id=1390

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 200, K = 200;

int d[N][N][K];
int color[N], len[N];
int n;

int sqr(int x){
    return x*x;
}

int f(int l, int r, int k){
    if (l>r) return 0;

    if (d[l][r][k]==0){
        if (l==r) d[l][r][k] = sqr(len[l]+k);
        else{
            d[l][r][k] = f(l, r-1, 0) + sqr(len[r]+k);
            for (int p=l;p<r;p++){
                if (color[p]==color[r])
                    d[l][r][k] = max(d[l][r][k], f(l, p, len[r]+k)  + f(p+1, r-1, 0));
            }
        }
    }
    return d[l][r][k];
}

void init(){
    int nn, tt, t;cin >> nn;

    n = 0;
    scanf("%d", &t);
    color[n] = t; len[n] = 1;

    for (int i=1;i<nn;i++){
        scanf("%d", &tt);
        if (tt==t) len[n]++;
        else color[++n] = tt, t = tt, len[n] = 1;
    }
    n++;

}
int main(){
    int T; cin >> T;
    for (int i=1;i<=T;i++){
        init(); memset(d, 0, sizeof(d));
        printf("Case %d: %d\n", i, f(0, n-1, 0));
    }
}

Posted by xiaodao
Category: POJ