(UVa) 10559 - Blocks

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1500

好難的DP

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAX_N = 306;

LL dp[MAX_N][MAX_N][MAX_N];
int a[MAX_N];

inline LL f(LL x) {
    return x*x;
}

int count[MAX_N],clr[MAX_N];

LL solve(int L,int R,int cnt) {
    if (dp[L][R][cnt] != -1) return dp[L][R][cnt];
    LL &ret=dp[L][R][cnt];
    if (L>R) return ret=0;
    if (L==R) return ret=f(cnt+count[L]);
    ret = max(ret,solve(L,R-1,0) + f(count[R]+cnt));
    LL tmp=0;
    int last=R-1;
    int ccnt=cnt;
    for (int i=L;R>i;i++) {
        if (clr[i] == clr[R]) {
            ret = max(ret,solve(L,i,cnt + count[R]) + solve(i+1,R-1,0));
        }
    }
//    ret = max(ret,f(ccnt+1) + solve(L,last,0));
//    bool check=true;
//    for (int i=L;R>=i;i++) {
//        check &= (a[i]==a[R]);
//    }
//    if (check) ret = max(ret,solve(L,last,0) + f(cnt+R-L+1));
    return ret;
}

int main () {
//    freopen("out10559.txt","w",stdout);
    int T;
    scanf("%d",&T);
    int kase=0;
    while (T--) {
        int n;
        scanf("%d",&n);
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
        }
        int id=0;
        memset(count,0,sizeof(count));
        for (int i=1;n>=i;i++) {
            if (a[i] == a[i-1]) count[id]++;
            else {
                ++id;
                clr[id] = a[i];
                count[id] = 1;
            }
        }
        memset(dp,-1,sizeof(dp));
        printf("Case %d: %lld\n",++kase,solve(1,id,0));
    }
}