没场切大人

Seaproyje · 2025-11-03 07:58:42 · 题解

场上没写完。

排列计数题，最不擅长。

看到 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 只有一个。