题解：P11274 「Diligent-OI R1 D」DlgtTemplate

· · 题解

题目传送门

思路

因为看着很 dp，所以往 dp 想。

然后就发现从前向后 dp 的后效性很大。

设 f_{i,j} 表示 [i,n] 中选出的需要把前面所选的 j 个元素的最大值。

于是我就开始犯错了。 首先，设 $psz_i$ 表示 $[1,i]$ 中 $b_i=0$ 的个数。 显然对于 $f_{i,j}$ ，仅当 $psz_{i-1} \ge j$ 时能取到。否则要删去的数会大于 $j$。而我首先想的是 $j<i$ 即可。 其次，我过不了样例 $4$ 在神秘力量的帮助下，我发现，我题目看少了。题目的有很特殊的地方。 最左边某些点会在逃过删除，而很显然逃过删除的只能是最左边的点。枚举该点，设下标为 $i$ 则 $i$ 后面选择的点的 $b_i$ 只能等于 $0$ 否则 $i$ 会被删。 于是就可以得出答案了。 因为算法是 $\mathcal{O}(n^2)$ 的，所以求方案很好求。