http://poj.org/problem?id=1390 (题目链接)
题意
给出一排方块，每次可以把颜色相同的消掉，获得长度的平方的分数，问最大得分。
Solution
蜜汁dp。。
我们把颜色相同的一段缩起来，$c[i]$表示第$i$段的颜色，$len[i]$表示第$i$段的长度。
$f[i][j][k]$表示将第$i$段到第$j$段，以及后面剩下来的跟第$j$段颜色相同的$k$个方块消掉的最大得分。考虑转移：
直接将第$j$段和它后面$k$个方块一起消掉。$$f[i][j][k]=f[i][j-1][0]+(len[j]+k)^2$$
后面$len[j]+k$个方块跟前面的第$pos$段颜色相同的一起消掉。$$f[i][j][k]=f[i][pos][len[j]+k]+f[pos+1][j-1][0]$$
我们用记忆化搜索，这样就不用讨论区间dp蛋疼的初始化了。
复杂度$O(n^4)$，不过远远达不到上界，信仰AC。
细节
多组数据注意清空。
代码
// poj1390
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf (1ll<<30)
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;const int maxn=210;
int f[maxn][maxn][maxn],c[maxn],a[maxn],len[maxn];
int n,m,Case;int dfs(int l,int r,int k) {
if (r<l) return 0;
if (f[l][r][k]!=-1) return f[l][r][k];
f[l][r][k]=dfs(l,r-1,0)+(len[r]+k)*(len[r]+k);
for (int i=l;i<r;i++)
if (c[i]==c[r]) f[l][r][k]=max(f[l][r][k],dfs(l,i,k+len[r])+dfs(i+1,r-1,0));
return f[l][r][k];
}
int main() {
int T;scanf("%d",&T);
while (T--) {
memset(c,0,sizeof(c));
memset(f,-1,sizeof(f));
memset(len,0,sizeof(len));
scanf("%d",&n);m=0;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++) {
if (a[i]!=a[i-1]) c[++m]=a[i],len[m]=1;
else len[m]++;
}
printf("Case %d: %d\n",++Case,dfs(1,m,0));
}
return 0;
}
