具体题目见 《算法艺术与信息学竞赛》P123
或 http://tyvj.cpwz.cn/Problem_Show.asp?id=1227 （可提交）
以下是代码（转自：http://www.cnblogs.com/jiaohuang/archive/2010/10/20/1856294.html）
1 /*
2 方块消除
3 先压缩下状态用把每种颜色压到一位，记录下每一位的长度
4 状态方程式dp[i][j][k] = max(dp[i][j-1][0] + (len[j]+k)^2 , dp[i][p][len[j]+k] + dp[p+1][j-1][0] )
5 k表示前面剩余的量。
6 */
7 #include <cstdio>
8 #include <cstring>
9 #include <algorithm>
10 using namespace std;
11
12 #define MX 210
13
14 int box[MX] , len[MX] , color[MX];
15 int f[MX][MX][MX] , L;
16
17 int Findmax(int a , int b , int rest){
18 if(f[a][b][rest] != -1)
19 return f[a][b][rest];
20
21 f[a][b][rest] = Findmax(a,b-1,0)+(len[b]+rest)*(len[b]+rest);
22 for(int i=a ; i<b ; i++)if(color[i] == color[b])
23 {
24 f[a][i][rest+len[b]] = Findmax(a , i , rest+len[b] );
25 f[i+1][b-1][0] = Findmax(i+1,b-1,0);
26 f[a][b][rest] = max( f[a][b][rest] , f[a][i][rest+len[b]] + f[i+1][b-1][0] );
27 }
28 return f[a][b][rest];
29 }
30
31 int main(){
32 int i , ncase;
33 int N , no=0;
34 scanf("%d" , &ncase );
35 while( ncase-- )
36 {
37 L = 0;
38 memset(len , 0 , sizeof( len ));
39 memset(f, -1 , sizeof(f));
40
41 scanf("%d" , &N);
42 for(i=0 ; i<N ; i++)
43 scanf("%d" , &box[i] );
44
45 int k = -1; //pre color
46 for(i=0 ; i<N ; i++)
47 {
48 if(box[i] != k)
49 {
50 L++;
51 k=box[i];
52 color[L] = box[i];
53 }
54 len[L]++;
55 }
56
57 for(i=0 ; i<=L ; i++)
58 f[i][i-1][0] = 0;
59 printf("Case %d: %d\n",++no , Findmax(1,L,0) );
60 }
61 return 0;
62 }