题解 P5322 【[BJOI2019] 排兵布阵】

一开始想了个复杂度爆炸的dp…… $f_{i,j}$ 表示前 $i$ 类城堡，获得了 $j$ 个城堡的最小花费 状态数是 $O(n^4)$ 的，转移是 $O(n)$ 的（在这里认为 $n$ 和 $s$ 同阶） 总时间复杂度是 $O(n^5)$ 的，神奇的有 $70pts$…… 考虑到 $m$ 只有 $20000$，不妨直接把 $m$ 压进去…… 设 $f_{i,j}$ 表示前 $i$ 类城堡，花了 $j$ 个兵，此时获得的最大收益 考虑第 $i$ 类城堡的时候，把所有玩家按照 $a$ 从小到大排序 然后枚举打败了几个玩家，假设打败的玩家中最大的 $a$ 是 $k$，显然只需要 $2k+1$ 个兵就够了 然后跑个背包就行了 时间复杂度是 $O(snm)$ 的，然后由于跑不满于是就过了……