poj 1390 Blocks - dblank

# poj 1390 Blocks

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 200 + 10, Mod = 1000000000;
typedef long long ll;
int dpN[N], n, k;
struct node
{
int c, l;
} p[N];
int solve(int i, int j, int len)
{
if(dpi[len]!=-1)
return dpi[len];
int res = (p[j].l + len)*(p[j].l + len);//和右边的同色块进行消除
if(i == j)
return res;
res += solve(i, j-1, 0);
for(int k = i; k<=j-1; k++)
{
if(p[k].c != p[j].c)
continue;
int sum = solve(k+1, j-1, 0);//把k和j之间的块消除的最大获得积分
sum += solve(i, k, len + p[j].l);//消除[i, k]区间，也就是k块和j块一起消除
res = max(res, sum);//取最大状态进行转移
}
return dpi[len] = res;
}
int main()
{
int t, x;
cin>>t;
for(int cas = 1; cas<=t; cas++)
{
int lastc = 0;
k = 0;
memset(dp, -1, sizeof(dp));
scanf("%d", &n);
for(int i = 1; i<=n; i++)
{
scanf("%d", &x);
if(x == lastc)
p[k].l++;
else
{
k++;
p[k].c = x;
p[k].l = 1;
lastc = x;
}
}
iterator
printf("Case %d: %dn",cas, solve(1, k, 0));
}
return 0;
}