题意：一个方块消除的游戏，每次可以消除颜色相同的方块，每次得分是你消除的格子的数量的平方。

黑书上的一题。

    参照《算法艺术》上的算法

 

    题目的方块可以表示称color[i],len[i],1<=i<=l

    这里l表示有多少"段"不同的颜色方块

    color[i]表示第i段的颜色,len[i]表示第i段的方块长度

    让f[i,j,k]表示把(color[i],len[i]),(color[i+1],len[i+1]),...,(color[j-1],len[j-1]),(color[j],len[j]+k)合并的最大得分

    这里k是可跟j合并的长度

    考虑(color[j],len[j]+k)这一段,要不马上消掉,要不和前面的若干段一起消掉

.................................................................

    1.如果马上消掉,就是f[i,j-1,0]+(len[j]+k)^2

    2.如果和前面的若干段一起消,可以假设这"若干段"中最后一段是p,则此时的得分是f[i,p,k+len[j]]+f[p+1,j-1,0]

 

    于是f[i,j,k] = max{f[i,j-1,0]+(len[j]+k)^2, f[i,p,k+len[j]]+f[p+1,j-1,0] }

     其中color[p]=color[j] ,i<=p<j 边界条件f[i,i-1,0]=0;

     

 

复杂度

 

    O(n^4),时间效率很低,但可以利用更新解的必要条件color[p] = color[j]来优化算法

Run ID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
9412246	201030720425	1390	Accepted	34432K	1938MS	G++	961B	2011-10-09 15:39:59
9412213	201030720425	1390	Accepted	33912K	1657MS	C++	961B	2011-10-09 15:33:45

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int len[205],dp[205][205][205],n,color[205],flag;
int DP(int x,int y,int k)
{if(dp[x][y][k])return dp[x][y][k];if(x==y) return (len[x]+k)*(len[x]+k);dp[x][y][k]=DP(x,y-1,0)+(len[y]+k)*(len[y]+k);for(int i=x;i<y;i++){if(color[y]==color[i]){dp[x][y][k]=max(dp[x][y][k],DP(x,i,len[y]+k)+DP(i+1,y-1,0));}}return dp[x][y][k];	
}
int main()
{int T,ans,tem;scanf("%d",&T);for(int t=1;t<=T;t++){scanf("%d",&n);flag=0;memset(len,0,sizeof(len));memset(color,0,sizeof(color));for(int i=0;i<n;i++){scanf("%d",&tem);if(color[flag]==tem)len[flag]++;else{flag++;len[flag]++;color[flag]=tem;}}memset(dp,0,sizeof(dp));ans=DP(1,flag,0);printf("Case %d: ",t);printf("%d\n",ans);}return 0;
}