【題意】：有一款方塊消除的游戲，游戲規則如下：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