引言
AGC018C Coins 因为不想写反悔贪心所以去学 wqs 二分。
wqs 二分 最初由王钦石在他的 2012 年国家集训队论文中提出，而从 IOI 2016 的 Aliens 题目开始，这种方法开始逐步在竞赛圈中有了一定的地位。在国内一般称为「wqs 二分」，而在国外一般称为「Alien Trick」。
算法引入
有 $n$ 个物品，物品 $i$ 的权值为 $w_i$，我们需要从中正好选择 $k$ 件物品，要求取出的物品总权值最大。
Solution 1
贪心，排序选出前 $k$ 个。
Solution 2
动规，设 $f_{i,j}$ 表示从前 $i$ 个物品中选出 $j$ 件可以获得的最大权值，可得：
$$f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1}+w_i)$$
时间复杂度 $O(n^2)$，如果没有限制的话可以压倒一维，时间复杂度也会降到 $O(n)$。
Solution 3
wqs 二分，设 $g_j$ 表示 $n$ 件物品中仅能取 $j$ 件的最大权值，即 $\max_{i=1}^{n}f_{i,j}$，且满足 $g_j-g_{j-1}\ge g_{j+1}-g_j$，斜率单调不增，是个上凸包。
++，不会了，有空再补。
挖坑待填
引用及参考
论文
博客