【题意】:有一款方块消除的游戏,游戏规则如下:n个带颜色方块排成一列,相同颜色的方块连成一个区域(如果两个相邻方块颜色相同,则这两个方块属于同一区域)。游戏时,你可以任选一个区域消去。设这个区域包含的方块数为x,则将得到x^2个分值。方块消去之后,其右边的所有方块就会向左移动,与被消去方块的左边相连。求游戏的最大得分。

【题解】:题目的方块可以表示成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], len[j] + k)合并的最大得分。
               考虑(color[j], len[j] + k)这一段,要不马上消掉,要不和前面的若干段一起消。
               1.如果马上消掉,就是f[i][j-1][0] + (len[j] + k) ^ 2;
               2.如果和前面的若干段一起消,可以假设这若干段中最后面得那一段是p,则此时的得分是f[i][p][len[j]+k] + f[p+1][j-1][0].
               于是有 f[i][j][k] = max(f[i][j-1][0] + (len[j] + k) ^ 2, f[i][p][len[j]+k] + f[p+1][j-1][0]),其中color[p] == color[r];
               显然 ans = f[1][l][0];               
               利用记忆化搜索来写,代码比较简洁。

【代码】:
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 210
 6 int n, val[maxn], cnt;
 7 int f[maxn][maxn][maxn];
 8 int len[maxn], color[maxn];
 9 
10 int calc(int x) {
11     return x * x;
12 }
13 
14 int dp(int l, int r, int k) {
15     if(f[l][r][k]) return f[l][r][k];
16     if(l == r) return f[l][r][k] = calc(k + len[r]);
17     f[l][r][k] = dp(l, r - 10+ calc(len[r] + k);
18     for(int i = l; i < r; i++
19         if(color[i] == color[r])
20             f[l][r][k] = max(f[l][r][k], dp(l, i, k + len[r]) + dp(i + 1, r - 10));
21     return f[l][r][k];
22 }
23 
24 int main() {
25     int T, Case = 1;
26     scanf("%d"&T);
27     while(T--) {
28         scanf("%d"&n);
29         for(int i = 0; i < n; i++) scanf("%d"&val[i]);
30         color[0= -1, cnt = 0;
31         for(int i = 0; i < n; i++) {
32             if(val[i] == color[cnt]) len[cnt]++;
33             else color[++cnt] = val[i], len[cnt] = 1;
34         }
35         memset(f, 0sizeof(f));
36         int ans = dp(1, cnt, 0);
37         printf("Case %d: %d\n", Case++, ans);
38     }
39     return 0;
40 }
41