题解

思路

在每次确实改变状态的操作中任选一个刚被涂黑的格子并依次记下。

做法

倒序观察这串格子：处理某个格子 $k$ 时，必须仍有一个包含它的可用区间，随后所有包含 $k$ 的区间都可以删去；从此以后，剩余区间不会跨过 $k$，问题便分裂为左右两个互不影响的子区间。因此令 $f_{l,r}$ 表示只保留完全包含在 $[l,r]$ 内的操作时的最大次数，枚举区间中最后被记下的格子 $k$，若存在一个完全包含在 $[l,r]$ 内且覆盖 $k$ 的操作，就有 $f_{l,r}=\max(f_{l,k-1}+f_{k+1,r}+1)$。这个倒序删除过程既说明任意合法操作序列都对应某次转移，也说明按转移递归合并左右序列一定能够实现，故状态转移恰好刻画最优值。

预处理 $cnt_{l,r}$ 表示端点均落在 $[l,r]$ 内的给定区间数。覆盖 $k$ 的候选区间存在，当且仅当 $cnt_{l,r}>cnt_{l,k-1}+cnt_{k+1,r}$；二维前缀关系可以在 $O(N^2)$ 时间求出全部 $cnt$，随后按区间长度递增计算动态规划。

复杂度

总时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。