http://poj.org/problem?id=1390

黑书上的例题，感觉我这辈子是想不到这样的dp了QAQ

\(f(i,j,k)\)表示将\(i\)到\(j\)合并，并且假设未来会有\(k\)个与\(a_j\)同色的方块与\(j\)相连的最大得分。

如果直接消去第\(j\)个区域和未来会接到\(j\)后面的\(k\)块,那么

\(f(i,j,k)=f(i,j-1,0)+(b_j+k)^2\)

如果\(j\)与之前一起合并，假设与\(j\)颜色相同的是区域\(p\)，那么

\(f(i,j,k)=f(i,p,k+b_j)+f(p+1,j-1,0),(i\leq p<j且a_p=a_j)\)

\(f(i,j,k)\)为两者的最大值。

答案即是\(f(1,n,0)\)

时间复杂度\(O(n^4)\)。

\(n^4\)竟然能过！一直在想\(n^3\)QwQ（说得好像我\(n^4\)能想出来一样TwT）

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 203;

int in() {

	int k = 0; char c = getchar();

	for (; c < '0' || c > '9'; c = getchar());

	for (; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - 48;

	return k;

}

int T, n, f[N][N][N], a[N], len[N], b[N], m;

int sqr(int x) {return x * x;}

int dp(int l, int r, int ex) {

	if (r < l) return 0;

	if (f[l][r][ex] != -1) return f[l][r][ex];

	int ans = dp(l, r - 1, 0) + sqr(len[r] + ex);

	for (int i = l; i < r; ++i)

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

			ans = max(ans, dp(l, i, len[r] + ex) + dp(i + 1, r - 1, 0));

	return f[l][r][ex] = ans;

}

int main() {

	T = in();

	for (int i = 1; i <= T; ++i) {

		printf("Case %d: ", i);

		memset(f, -1, sizeof(f));

		memset(len, 0, sizeof(len));

		m = in();

		for (int j = 1; j <= m; ++j)

			b[j] = in();

		a[n = 1] = b[1]; len[1] = 1;

		for (int j = 2; j <= m; ++j)

			if (b[j] != b[j - 1]) {

				a[++n] = b[j];

				len[n] = 1;

			} else

				++len[n];

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

	}

	return 0;

}