题意：有一排box，各有不同的颜色。你可以通过点击某个box使得与其相邻的同色box全部消掉，然后你可以得到的分数为消去长度的平方，问怎样得到最高分？
题解：考虑用一维dp，/*dp[i]为1~i个block（我们称颜色相同的一段box为一个block）所能得到的最大得分*/发现无法递推。
考虑用二维dp，dp[i][j]为从block i 到 block j 的最大得分
考虑最右端的j1.直接消除j
2。它和左边的某个block合并：dp[i][k-1]+dp[k+1][j-1]+(len[k]+len[j])^2
发现无法计算，因为合并一块以后还能继续合并，可能得到更优解。
所以用三维dp dp[i][j][extra_len] 代表从block i 到block j ,且将j右边长为extra_len的box与 bolck j 合并时（也就是说其颜色与j相同）能取得的最大值。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = ;
struct block {
int color;
int len;
}segment[maxn];
int score[maxn][maxn][maxn];
int click_box(int start, int end, int extra_len) {
int i, res, temp;
int &now = score[start][end][extra_len];
if (now> )return now;//记忆递归
res = segment[end].len + extra_len;
res *= res;
if (start == end) { return now = res;}//递归边界
res += click_box(start, end - , );//直接消掉extra_len+end
for (i = end - ; i >= start; i--) {
if (segment[i].color != segment[end].color)continue;
temp = click_box(start, i, segment[end].len + extra_len)+click_box(i+,end-,);//找到前面某个i 一起消掉
if (temp <= res)continue;
res = temp;
}
now = res;
return now;
}
int main() {
int t, n, i, j, end, color;
cin >> t;
for (int i = ; i <= t; i++) {
cin >> n; end = ;
cin >> segment[end].color;
segment[end].len = ;
for (j = ; j < n; j++) {
cin >> color;
if (color == segment[end].color)segment[end].len++;
else end++, segment[end].color = color, segment[end].len = ;
}
memset(score, , sizeof(score));
cout << "Case " << i << ": " << click_box(, end, ) << endl;
}
system("pause");
//return 0;
}