大佬教程收集整理的这篇文章主要介绍了经典区间dp 【方块消除】，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题目传送门~

思路

求一个区间内分数的最大值，我们容易想到用区间dp来做这道题。

首先，我们来定义一下数组：

(dp[l][r]) 表示 将 (l)~(r) 这段区间消除得到的最大分数值。 (color[l]) 表示 (l) 这段区间的颜色。 (len[l]) 表示 (l) 这段区间的长度。

但是在写代码时，我们发现：如果在 (r) 后面有一段长度为 (k) 的区间颜色和 (r) 区间 一样，那么在消除 (l)~(r) 区间时，会顺带着把 (k) 区间也消除了。所以我们就加上一维数组来维护这个 (k) ：

(dp[l][r][k]) 表示 消除 (l)~(r) 这段区间且在 (r)区间 后有 (k) 个与 (r) 区间颜色相同的方块的最大分数值。

接下来我们考虑状态的转移。

1. 首先，我们可以直接消除 (r) 这一段区间，再加上消除 (l) ~ (r-1) 区间的最大值，那么转移方程就为：
   [dp[l][r][k] = dp[l][r-1][0] + (len[r] + k)^2 ]

2. 其次，我们可以枚举 (l)~(r) 间的一段区间 (i)，使 (i) 区间的颜色与 (r) 区间的颜色相同，然后我们可以先消除 (i+1) ~ (r-1) 区间。这样的话， 就可以将 (r) 和 (i) 两个区间合并成一个颜色相同的区间，然后再计算消除 (l)~(i) 区间的最大值，那么转移方程就为：
   [dp[l][r][k] = max (dp[l][i][len[r] + k] + dp[i +1][r -1][0]) ]

3. 当然，(l == r) 时，我们直接返回 ((len[r]+k) ^2) 即可。

代码

记忆化搜索

#include <cstdio>
using namespace std;

inline char nc () {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 100000, stdin), p1 == p2) ? EOF :*p1++;
}

inlinE int read () {
	register int x(0), f(1);
	char ch = nc ();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = ~f +1;
		ch = nc ();
	}
	while (ch <= '9' && ch >= '0') {
		x = (x << 3) + (x << 1) + (ch ^48);
		ch = nc ();
	}
	return x *f;
}
 
inlinE int max (int a, int b) {
	return a > b ? a :b;
}

int n;
int color[55];
int len[55];
int qwq[55][55][555];

int dfs (int l, int r, int k) {
	if (qwq[l][r][k]) return qwq[l][r][k];
	if (l == r) return (len[r] + k) * (len[r] + k);
	qwq[l][r][k] = dfs (l, r - 1, 0) + (len[r] + k) * (len[r] + k);
	for (register int i(l); i < r - 1; ++i)
		if (color[i] == color[r])
			qwq[l][r][k] = max (qwq[l][r][k], dfs (l, i, len[r] + k) + dfs (i + 1, r - 1, 0));
	return qwq[l][r][k];
}

int main () {
	n = read ();
	for (register int i(1); i <= n; ++i) color[i] = read ();
	for (register int i(1); i <= n; ++i) len[i] = read ();
	printf ("%d", dfs (1, n, 0));
	return 0;
}

大佬总结

以上是大佬教程为你收集整理的经典区间dp 【方块消除】全部内容，希望文章能够帮你解决经典区间dp 【方块消除】所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。