题解：CF1739E Cleaning Robot

灵茶山艾府 · 2025-04-26 09:22:40 · 题解

目前已有题解（包括官方题解）都写得很麻烦，我来提供一个简单的思路和简洁的写法。

不失一般性，假设机器人在第一行（上面那行）。

情况一：无论机器人下方是否有污渍，都可以让机器人向右走。

• 如果机器人下方没有污渍，那么机器人只能向右走。（或者说只需考虑向右走）
• 如果机器人下方有污渍，那么我们擦掉污渍，机器人就只能向右走了。

情况二：如果机器人下方有污渍，可以让机器人向下走。

• 如果机器人右边没有污渍，那么机器人只能向下走。
• 如果机器人右边有污渍，那么我们擦掉污渍，机器人就只能向下走了。
• 机器人向下走后，下一步一定向右走，并且（因为我们擦掉了污渍）下下一步也是向右走。这个性质很有用，我们无需额外用一个参数记录「擦掉了右边的污渍」。

下面计算我们自己最少要擦掉多少污渍。

定义 f_{j,i} 表示机器人在 i 行 j 列时，我们自己最少要擦掉多少污渍。（下标从 0 开始）

• 情况一：f_{j,i} = f_{j+1,i} + a_{i\oplus 1, j}。
• 情况二：如果 a_{i\oplus 1, j}=1，那么有 f_{j,i} = f_{j+2,i\oplus 1} + a_{i, j+1}。

两种情况取最小值，就是 f_{j,i}。

初始值：f_{n-1,i} = f_{n,i} = 0。

答案：\texttt{1} 的总个数减去 f_{0,0}，因为一开始在 (0,0)。

AC 代码（Golang）：

package main
import("bufio";."fmt";"os";."strings")

func main() {
    var n int
    a := [2]string{}
    Fscan(bufio.NewReader(os.Stdin), &n, &a[0], &a[1])
    f := make([][2]int, n+1)
    for j := n - 2; j >= 0; j-- {
        for i := range 2 {
            f[j][i] = f[j+1][i] + int(a[i^1][j]&1)
            if a[i^1][j] == '1' {
                f[j][i] = min(f[j][i], f[j+2][i^1]+int(a[i][j+1]&1))
            }
        }
    }
    Print(Count(a[0], "1") + Count(a[1], "1") - f[0][0])
}

时间复杂度：\mathcal{O}(n)。

欢迎关注 B站@灵茶山艾府