自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 22:29:39，当前版本为作者最后更新于2021-03-06 19:56:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7414 题解

不是，USACO 恶意撞题怎么回事啊/yiw

Description

有一个长度为 $n$ 的初始值均为 $0$ 的序列 $a$，每次操作可以将其中一个子段统一改成任意值。

现给定一个长度为 $n$ 的目标序列 $b$，求最少操作几次可以达到这个目标序列。

Solution

$dp$ 显然。

考虑设 $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)$。