poj 1390 Blocks

题意

一排带有颜色的砖块，每一个可以消除相同颜色的砖块，，每一次可以到块数k的平方分数。问怎么消能使分数最大。。

题解

此题在徐源盛《对一类动态规划问题的研究》以及刘汝佳的黑书《算法艺术与信息学竞赛》中都有提及。

首先我们要将相同颜色块进行合并。定义状态\(dp[i][j][k]\)表示第\(i\)到第\(j\)个颜色块后面接了\(k\)个颜色为\(color[j]\)的砖块。

不难得出转移方程为\(dp[i][j][k]=max \{ dp[i][j-1][0]+(len[j]+k)^2, dp[i][p][k+len[j]] + dp[p+1][j][0] \}\)

我们可以记录一下上一次\(color[j]\)出现的位置，就可以在\(O(n^3)\)内完成问题。

此题我写的是递推，不过记忆化似乎更快

递推

#include <cstdio>

#include <cstring>

const int N = 205;

int dp[N][N][N], color[N], len[N], pre[N], pos[N];

inline void SelfMax(int &a, const int &b) { if (a < b) a = b; }

inline int p2(const int &a) { return a * a; }

int main() {

	int n, pr, i, j, k, T, tot, a, Sizdp = sizeof dp, length, Case = 0;

	scanf("%d", &T);

	while (T--) {

		n = 0; pr = -1; scanf("%d", &tot);

		for (k = 1; k <= tot; ++k) {

			scanf("%d", &a);

			if (a != pr) color[++n] = pr = a, len[n] = 1;

			else ++len[n];

		}

		memset(dp, 0, Sizdp); memset(pos, 0, sizeof pos);

		for (i = 1; i <= n; ++i) pre[i] = pos[color[i]], pos[color[i]] = i;

		for (length = 1; length <= n; ++length)

		  for (i = 1;; ++i) {

			  if ((j = i + length - 1) > n) break;

			  for (k = 0; k <= tot; ++k) {

				  dp[i][j][k] = dp[i][j-1][0] + p2(len[j] + k);

				  for (a = pre[j]; a >= i; a = pre[a])

					SelfMax(dp[i][j][k], dp[i][a][k+len[j]] + dp[a+1][j-1][0]);

			  }

		  }

		printf("Case %d: %d\n", ++Case, dp[1][n][0]);

	}

	return 0;

}

记忆化

#include <cstdio>

#include <cstring>

const int N = 205;

int dp[N][N][N], color[N], len[N], pre[N], pos[N], Sum[N];

inline void SelfMax(int &a, const int &b) { if (a < b) a = b; }

inline int p2(const int &a) { return a * a; }

int f(int i, int j, int k) {

	if (~dp[i][j][k]) return dp[i][j][k];

	if (i > j) return 0;

	int &ret = dp[i][j][k];

	ret = f(i, j-1, 0) + p2(k + len[j]);

	for (int p = pre[j]; p >= i; p = pre[p]) SelfMax(ret, f(i, p, k + len[j]) + f(p+1, j - 1, 0));

	return ret;

}

int main() {

	int n, pr, i, j, k, T, tot, a, Sizdp = sizeof dp, length, Case = 0;

	scanf("%d", &T);

	while (T--) {

		n = 0; pr = -1; scanf("%d",&tot);

		for (k = 1; k  <= tot; ++k) {

			scanf("%d", &a);

			if (a ^ pr) color[++n] = pr = a, len[n] = 1;

			else ++len[n];

		}

		memset(dp, -1, Sizdp); memset(pos, 0, sizeof pos);

		for (i = 1; i <= n; ++i) pre[i] = pos[color[i]], pos[color[i]] = i;

		printf("Case %d: %d\n", ++Case, f(1, n, 0));

	}

	return 0;

}