Description：

有一排 $n$ 个正方体每个都有颜色，每次可以消去颜色相同的一段获得长度的平方的价值，最大化消完得到的总价值。

$1\le n \le 200$

Solution：

看上去是个区间 $DP$ ，但所有直接 $DP$ 的做法似乎都是错的，因为可以把很多段合起来，而一些可以合的有时候还不能合，这题状态定义为 $f[i][j][k]$ 表示 $[i,j]$ 区间后面还有 $k$ 个和 $j$ 颜色相同的（不包括 $j$ ）的最大价值，转移时要么直接删掉右面那些： $f[l][r][k]=f[l][r-1][0]+(k+1)^2$ ，要么再和前面的一个合并，即在前面找一个和 $r$ 颜色相同的位置 $p$ ，把 $p+1$ 到 $r-1$ 化为一段消去，即 $f[l][r][k]=f[l][p][k+1]+f[p+1][r-1][0]$ 。

注意只有合法的状态才能递归进入。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 201

int col[MAXN];

int f[MAXN][MAXN][MAXN];

int dp(int l,int r,int k)

{

	if(l > r)return 0;

	if(f[l][r][k])return f[l][r][k];

	f[l][r][k] = dp(l,r - 1,0) + (k + 1) * (k + 1);

	for(int i = r - 1;i >= l;--i)

		if(col[i] == col[r])

			f[l][r][k] = max(f[l][r][k],dp(l,i,k + 1) + dp(i + 1,r - 1,0));

	return f[l][r][k];

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	for(int t = 1;t <= testcases;++t)

	{

		scanf("%d",&n);

		for(int i = 1;i <= n;++i)scanf("%d",&col[i]);

		memset(f,0,sizeof(f));

		printf("Case %d: %d\n",t,dp(1,n,0));

	}

	return 0;

}