治程212

Union_of_Britain · 2024-12-03 18:27:03 · 个人记录

题解对于 f(i,j) 关于 j 在一段单调要么没有说明，要么说明过繁。

最优解一定是极优的。因此，在一个方案中（钦定这个方案把“中立位置”选完），如果在 i 位置之前有 j-1 个已选位置，后面选择位置是 a 和是 S，并且 i 是已选位置，此时取消选择 i 一定是不优的：

如果 i 是未选位置，选上 i 一定是不优的：

这两边显然是无交，并且依靠 j 分界的。

这也直接说明了贪心的正确性：一个位置被选择，之后也会被选择。（这个证明简易多了！）