NOI2022 D1T2 移除石子

手玩 $l_i = r_i, k = 0$ 的情况，如果不存在 $a_i = 1$ 的情况直接用操作 $1$ 就行了，否则一定是用若干段不交操作 $2$ cover 掉了所有 $a_i = 1$​ 的段。称这样的操作为“一层操作”。

在这样一层操作之后可能会使得 $a_i = 2$ 的位置变成新的 $a_i = 1$，继续进行若干层操作。

发现有以下性质：

• 操作 $2$ 长度只可能是 $3, 4, 5$
• 同一个左/右端点不可能同时有长度为 $4, 5$​​ 的操作
• 同一个位置至多被 $3$​ 个操作覆盖（先默认它成立，结合后面的 DP 只需要证 $j = 2, k = 2$ 的情况，只有 $4$ 种 Case 可以手摸）
• 值域 $\ge 4$ 和 $4$ 等价

恰好加入 $k$ 个石子改成至多放入 $k$ 个石子：

• 实际取的 $< k - 1$ 或 $= k$ 或存在操作 $1$ ：无影响
• 不存在操作 $2$ ，即全 $0$：在 $k = 1$ 时有影响
• 存在操作 $2$ 且 $n = 3$：只可能是 $1, 1, 1$ 这种情况，$k\ge 2$ 可以用操作 $1$ 替代，$k = 1$ 时有影响

所以只需要特判 $k = 1$ 时 ${0, 0,\cdots}$ 和 $1, 1, 1$ 两种 case。

然后考虑 DP，设 $f(i, j, k)$ 表示前 $i$ 个处理了，强制 $j$ 个至少拓展到 $i + 1$，$k$ 个到 $i + 2$。（$j + k\le 3$）

转移时考虑枚举在 $i + 1$ 处新加 $0\sim 2$ 个操作 $2$，有 $x\le j$ 个强制到 $i + 1$ 的操作强制变到 $i + 2$。

$l_i\ne r_i$ 的情况，将上述 DP 改成 DP of DP，这一部分非常套路，直接搜内层 DP 数组大小为 $10$，状态数为 $10012$，已经可以通过。

根据上面分析的性质可以有以下剪枝：

• $4, 5$ 不能同时出现，所以 $j = 3, k = 0$ 和 $j = 0, k = 3$ 没用
• $x$ 至多为 $1$，原因同上条

DP 数组大小就变成了 $8$，状态数也优化到了 $6258$，优于大部分题解 $8000\sim 9000$ 的状态数。