【题意】：有一款方块消除的游戏，游戏规则如下：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 - 1, 0) + 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 - 1, 0));
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, 0, sizeof(f));
36 int ans = dp(1, cnt, 0);
37 printf("Case %d: %d\n", Case++, ans);
38 }
39 return 0;
40 }
41