题解 P7414 【[USACO21FEB] Modern Art 3 G】
Unordered_OIer
·
·
题解
P7414 题解
不是，USACO 恶意撞题怎么回事啊/yiw
Description
有一个长度为 n 的初始值均为 0 的序列 a，每次操作可以将其中一个子段统一改成任意值。
现给定一个长度为 n 的目标序列 b，求最少操作几次可以达到这个目标序列。
Solution
考虑设 $f[i][j]$ 表示刷完区间 $[i,j]$ 至少需要多少次。
假设当前决策到 $i,j$，分类讨论：
- $b_i \neq b_j$，则考虑枚举一个分段点 $k$，依次转移即可，即：
$$f[i][j]=\min\limits_{k=i}^{j-1}f[i][k]+f[k+1][j]$$
- $b_i=b_j$，则容易得到 $f[i][j] \geq f[i+1][j]$，并且观察到 $f[i+1][j]$ 的任意一种方案都会适合 $f[i][j]$，延申一个底盘即可，因此 $f[i][j] \leq f[i+1][j]$。
综上，得到 $f[i][j]=f[i+1][j]$，但是因为左右延申都是可以的，所以 $f[i][j]=\min(f[i+1][j],f[i][j-1])$，即：
$$f[i][j]=\min(f[i+1][j],f[i][j-1])$$
所以通过讨论我们得到了转移方程：
$$f[i][j]=\begin{cases}\min\limits_{k=i}^{j-1}f[i][k]+f[k+1][j]&b_i \neq b_j\\\min(f[i+1][j],f[i][j-1])&b_i=b_j\end{cases}$$
初始化即为 $f[i][j]=\begin{cases}∞&i \neq j\\1&i=j\end{cases}$。
转移即可，复杂度 $\mathcal O(n^3)$。