提供一个 O(klogk) 不依赖 n 的做法。
不难想到类似 [NOI2010] 超级钢琴 的思路。
我们考虑方案与方案之间的转移。
对于方案 S ，记 trans(S) 为 S 的后继方案集合（具体定义暂不明确）。
我们按以下流程求解问题。
-
将花费最小的方案加入小根堆中
-
重复执行直到堆为空，或已得到所有答案
考虑怎样设计 trans(S) 才能使得这个算法正确。
首先将 a 数组排序。
特判掉 k=1 的情况，现在假设 n=5 。
然后往小根堆里加入一个初始状态： {c}={1,0,0,0,0} 。
现在就有两条路可走：
-
第一位加 1 ： {c}={2,0,0,0,0}
-
将 +1 往后挪，并且这个新的状态只能在挪过去的那一位及之后加一，或者继续挪：
比如挪了之后： {c}={0,1,0,0,0} ，那么它的后继只能是：
-
{c}={0,2,0,0,0}
-
{c}={0,0,1,0,0}
注意我的表述是 +1 往后挪，比如 {c}={2,0,0,0,0} 可以转移到 {c}={3,0,0,0,0} 或者 {c}={1,1,0,0,0} 。
请耐心思考一下，这样构造下去，定能不重不漏的得出所有的 c 数组，并且后加入堆的肯定比先加入的大（因为 a 的值为正）。
注意到我们并不关心 c 数组长啥样子，只关心它的和，以及它现在挪到了哪一位。
所以 S 应该包括两个状态 (sum,pos) 。
最终我们按如下的方法构造 trans(S) ：
-
(sum+apos,pos)
-
(sum−apos+apos+1,pos+1) ∣ pos<n
这就是为什么一开始加入的是 {c}={1,0,0,0,0} 这个状态，因为 {c}={0,0,0,0,0} 根本没有 +1 又怎能往后挪。。。
显然堆中最后只有 2k 个元素，时间复杂度 O(klogk) 。
code
京公网安备 11010502036488号