没场切大人

场上没写完。

看到 $n \le 500$，大概就是 $O(n^3)$，设 DP 那么肯定有两维是填了几个数和能通过的 $c_i$ 的下界（对于 $s_i = 1$）。

冥想一下， 设$f_{i,j,k}$ 为填了前 $i$ 个，填了 $j$ 个 $c_x\ge k$，$k$ 即为能通过的 $c_x$ 的下界。

考虑 $k+1$ 会发生什么，发现 $j$ 会减去 $c_x = k$ 的个数，但我们很显然不知道怎么办呢？

一个看起来很荒谬的想法是直接枚举，但这是对的，因为对于选了一个 $\ge k$ 的数，我们并不需要直接得知他具体是多少，只需要在需要得知的时候随意指定即可，于是大概思路就有了。

看上去是 $O(n^4)$ 的，实际上对于所有的 $k$ 枚举的总和是 $O(n)$ 的，所以是$O(n^3)$。

最后统计答案时枚举 $k$，合法的 $j$ 只有一个。