CF1739E Cleaning Robot

Alex_Wei · 2022-12-17 19:26:25 · 题解

首先，因为只有两列且机器人只会向最近的格子移动，所以机器人一定不会向左移动。

对于前 i 列，我们只关心机器人在清扫完毕后的行，设为 j。转移到第 i + 1 列时，如果两行都没有或只有第 j 行有，则保持 j 不变。否则机器人要么走到 (i, j \oplus 1)，要么先走到 (i, j) 再走到 (i, j\oplus 1)，这两种情况均要求 (i + 1, j) 为空，否则机器人会爆炸，我们在 DP 时记录下一列的每一行（实际上只关心第 j\oplus 1 行）是否必须为空即可。

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