[ABC145F] Laminate 题解

想必大家都会积木大赛。

若修改 ，考虑如何让它带来的贡献最小。根据积木大赛的结论，只需让 ，这个位置就不会带来任何的贡献，可以认为我们删除了第 个位置。显然，，总存在 满足以上条件。

那么问题就变成了，原本有 个位置，可以删除最多 个位置，求最小答案。于是自然而然地想到了 DP。

设 表示现在在第 个位置，删除了 个位置，上一个没有被删除的位置是 的最小答案。转移方程：

时间复杂度 。

提交记录。