Paint 题解
August_Light
·
·
题解
Paint 题解
题目传送门
写在前面
从模拟赛赛题 YACS 835 来的。
题意简述
保证每一种颜色初始时在序列中最多只有 $p$ 个位置。
$t \le 10^3, \sum n \le 3 \times 10^3, a_i \le n, p = 20$。
## 前置知识
- 区间 DP
## 解法
数据范围小但不完全小，先考虑区间 DP。
设 $f_{l,r}$ 为 $[l,r]$ 变为同一颜色的最小操作数。
然后不会做了。
~~写一个 $O(\frac {n^4} w)$ 的 bitset 优化 DP~~
~~为了方便转移，我们猜出一个结论~~：对于一个区间 $[l,r]$，必定存在一种最优方案使得最终颜色为 $a_r$，也就是说能保住区间端点的颜色。
事实上这是对的：
- $l = r$ 显然成立。
- 如果 $[l,r-1]$ 存在全部变为 $a_r$ 的最优方案，那么成立。
- 如果 $[l,r-1]$ 不存在全部变为 $a_r$ 的最优方案，那么必须花费一步把 $[l,r-1]$ 和 $a_r$ 统一，此时把 $[l,r-1]$ 染成 $a_r$ 即可。
DP：
枚举断点 $k$，如果 $a_k = a_r$，那么说明不需要额外染色；否则就要额外染一次。
$$f_{l,r} = \begin{cases} 0 & l = r \\ \min\limits_{k=l}^{r-1}(f_{l,k} + f_{k+1,r} + [a_k \ne a_r]) & \text{otherwise} \end{cases}$$
以上方法时间复杂度 $O(n^3)$。
$p = 20$ 的限制还没用上。
当 $a_k \ne a_r$ 时，这种方案肯定没有 $a_k = a_r$ 要好，因为需要一步来统一两个区间的颜色。
所以找到每一个 $a_k = a_r$ 的地方对 $f_{l,k} + f_{k+1,r}$ 取 $\min$ 即可。
不要忘记 $f_{l,r} \gets f_{l,r-1} + 1$ 保个底。
以上方法时间复杂度 $O(n^2 p)$。
## 代码
```cpp
#include <bits/stdc++.h>
#define memset0(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long LL;
// 省略快读快写的实现
void chkmin(int &x, int y) {
x = min(x, y);
}
const int MAXN = 3e3 + 5;
const int INF = MAXN;
int n;
int a[MAXN];
int pre[MAXN], lst[MAXN];
int f[MAXN][MAXN]; // f[l][r] = 把 [l,r] 统一为 a[r] 的最小次数
int main() {
for (int t = read(); t--;) {
int n = read();
for (int i = 1; i <= n; i++)
a[i] = read();
memset0(pre); memset0(lst);
for (int i = 1; i <= n; i++) {
pre[i] = lst[a[i]];
lst[a[i]] = i;
}
for (int len = 1; len <= n; len++) {
for (int l = 1, r = l + len - 1; r <= n; l++, r++) {
if (len == 1) {
f[l][r] = 0;
continue;
}
/* 暴力做法：
f[l][r] = INF;
for (int k = l; k+1 <= r; k++)
chkmin(f[l][r], f[l][k] + f[k+1][r] + (a[k] != a[r]));
*/
// 正解
f[l][r] = f[l][r-1] + 1;
for (int k = pre[r]; k >= l; k = pre[k])
chkmin(f[l][r], f[l][k] + f[k+1][r]);
}
}
write(f[1][n], '\n');
}
return 0;
}
```