AcWing 322. 消木块

由于木块可以由一些木块的消除，使两边相同颜色的合并

所以我们设定一个归并方式，即每个区间记录一下右边的延展性。

（等于左边找右边）

设 \(f[i][j][k]\) 为\([i, j]\) 区间，右侧有 \(k\) 个颜色 \(= a[j]\) 的。

考虑两种转移方式。

第一种操作：直接搞掉右边的。

设 \(i <= p <= j\)，且 \([p, j]\) 区间内的颜色都是 \(a[j]\)。

那么把右边的搞掉即可，

\(f[i][p - 1][0] + (k + j - p + 1) ^ 2\)

第二种操作：考虑把 \([q + 1, p - 1]\) 这段搞掉，然后左边和右边的合并。

即找一个位置 \(i <= q < p - 1\); 且满足 \(a[q] = a[j]\)

\(f[q + 1][p - 1][0] + f[i][q][k + j - p + 1]\)

一个剪枝，保证 \(a[q] \not= a[q + 1]\)，否则肯定不优。

值得注意的是边界问题

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N = 205;

int n, a[N], f[N][N][N];

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

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

	int &v = f[l][r][k];

	if (l == r) return v = (k + 1) * (k + 1);

	int p = r;

	while (p - 1 >= l && a[p - 1] == a[r]) p--;

	v = (p == l ? 0 : dp(l, p - 1, 0)) + (k + r - p + 1) * (k + r - p + 1);

	for (int q = l; q < p - 1; q++) {

		if (a[q] == a[r] && a[q] != a[q + 1])

			v = max(v, dp(q + 1, p - 1, 0) + dp(l, q, k + r - p + 1));

	}

	return v;

}

int main() {

	int T; scanf("%d", &T);

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

		memset(f, -1, sizeof f);

		scanf("%d", &n);

		for (int i = 1; i <= n; i++) scanf("%d", a + i);

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

	}

	return 0;

}

巴特西

AcWing 322. 消木块

最新文章

热门文章