题解：P8029 [COCI2021-2022#3] Akcija

· · 题解

很经典的前 k 优方案的问题。目前大概看过两种类型，一个是类似于局部选择可以排序一下，然后维护指针不断加入。另一个是像本题这样子类似全局选可以考虑 \operatorname{A*}。维护一个估计函数 f 代表后缀最优代价， 然后从 1 开始顺推。

放到图上形式化地描述就是前者是离源点最近的 k 个点，可以维护指针不断扩展。后者是 k 短路，需要我们用 \operatorname{A*} 来解决。

本题的实现方法就是先求出 $f_{i,j}$ 表示后面 $n-i$ 个物品我们选择了 $k-j$ 个的最小代价。也就是一个后缀最优函数。这个很容易通过 dp 来求解。 然后我们从 $1$ 开始顺推，设当前局面状态为 $s$ 前缀代价为 $g_s$。我们只需要维护前 $k$ 大的 $g_s+f_s$ 即可。因为 $f_s$ 仅仅表示后缀最小代价，可能还会有次小等等之类，也就是说 $s$ 后面可能会扩展出多个状态，其中一个最好的情况是 $f_s+g_s$。故当前局面的前 $k$ 优可以推出最后局面的前 $k$ 优。而当前局面的第 $k+1$ 优的最佳情况已经不如前 $k$ 个状态优了，所以必定不可能成为最后的前 $k$ 优方案。 有一个技巧就是我们并不需要维护前 $k$ 状态的相对大小，只需要找到前 $k$ 小，所以直接用 `nth_element` 函数即可，而不用排序或者优先队列，可以省去一个 $\log$ 的复杂度。 时间复杂度 $O(n^2+nk)$。