题解 P2135 【方块消除】
Froranzen
·
·
题解
题目传送门~
思路
求一个区间内分数的最大值，我们容易想到用区间dp来做这道题。
首先，我们来定义一下数组：
$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$ 即可。
------------
# 代码
### 记忆化搜索
```cpp
#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;
}
```
------------
（悄悄[要个关注](https://www.luogu.com.cn/user/361432)不过分吧, qwq）