论文 提出问题 在某些题目中，强制规定只能选 k 个物品，选多少个和怎么选都会影响收益，问最优答案。 算法思想 对于上述描述的题目，大部分都可以通过枚举选择物品的个数做到 O(nk2) 或 O(nk) 的 DP，如果没有选择个数的限制的话，复杂度大概会降为 O(n) 级别。 先不考虑数量限制。 假设要最小化权值。 还是拿题说吧：给定长度为 n 的正整数序列，要求将该序列划分为 k 段，记每段之和为 sum(i)，求最小的 k ∑ i=1 sum(i)2。 如果没有段数限制，那我们肯定是每个数分成一段对吧。 如果加上段数限制呢？ 先放上结论：打表可得如果以段数 k 为横坐标，以该段数求得的最小和 f(k) 为纵坐标，把这 n 个点放在平面直角坐标系上，那么形成的图形会是一个上凸包。也就是相邻两点的斜率单调不增。 那就可以考虑wqs二分了。 注意当前的问题是：我们知道这个图形是一个上凸包，但是并不知道具体的 (x,f(x)) 坐标。 我们可以二分一个权值 mid，这个 mid 表示，我们要拿一条直线去切当前这个凸包，这个直线的斜率为 mid。因为是上凸包，那这条直线肯定会在交某个点 (x,f(x)) 时截距取到最小值。设当前截距为 g(mid)。 直线可以表示成 y=kx+b，所以 f(x)=mid⋅x+g(mid)。 移项，g(mid)=f(x)−mid⋅x。 观察上面的等式，如果当前横坐标为 x 的话，g(mid) 恰好是 f(x) 减去 x 个 mid。 f(x) 不好求，那我求出来 g(mid)，再顺便求出来 x 不就行了吗。 也就是说，如果能求出截距 g(mid)，并且知道当前切到点的横坐标 x，那就可以求得 f(x)，并且可以根据 x 和题目中的 k 来调整 mid 了。 回到题目，我们假设当前没有分 k 段这个限制，但是多了一个条件，每分一段都需要将代价额外加上 mid 。 在这个条件下，我们做一遍没有取物品限制的DP，得出当前的最优解 a 和取最优解时候分出的段数 b，那就有 g(mid)=a,x=b。 这样就能求出来 f(x) 了。 但是关键不在 f(x)，而在这个 x。如果使用的这个 x 大于题目中的 k，那就得增大这个 mid，感性理解一下，代价增多了分的段数才会少，反之就要减少 mid。 这样通过二分就可以找到一条恰好切于 (k,f(k)) 这个点的直线，进而就知道答案 f(k) 了。 还有一个问题没有解决，如果我们二分不出来这个具体的 k 怎么办，也就是说，凸包上出现三点共线的情况怎么办。 如果这样，我们就再额外添加一个规则，比如说在满足 g(mid) 为最大权值的情况下使得 x 最小。这样就知道直线的最左端点 t 了。又因为斜率和截距是相同的，所以即使 t!=k 拿截距 g(t)−k⋅mid 也还是最终的答案。 例题 [国家集训队2] Tree I Description 给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 k 条白色边的生成树。题目保证有解。 Sol 这就是wqs二分裸题了。二分一个 mid，然后把所有白边的边权加上 mid，然后求一下当前的花费和用了几条白色边，然后动态调整即可。 这里有一个细节就是会出现白边和黑边边权相等的情况，这时候就要用到上边的做法，强制规定一个规则。假设我们规定相等时先用白边，那二分就这么写： while(l<=r){ int mid=l+r>>1;check(mid); if(used>=k) ans=mid,l=mid+1; else r=mid-1; } 关键在于是 used>k 时记录 mid 还是在 used=k 时记录 mid。 代码 [Luogu4983] 忘情 Description 定义一段序列的值为 (( n ∑ i=1 xi× ˉ x )+ ˉ x ) ˉ x 2 ，其中 n 为该序列长度。 给定长度为 n 的序列，要求分为 m 段，使得每一段的值的和最小。 Sol 把这个式子拿出来推一推，发现这就是个斜率优化的式子了。 然后就套路二分 mid，check的时候用斜率优化 O(n) 求就行了。 md这题wa了好几次竟因define没加括号身败名裂 代码 [CF739E] Gosha is hunting Description 有 a 个宝贝球和 b 个大师球。对于每个神奇宝贝，用宝贝球抓到的概率为 pi，用大师球抓到的概率为 qi （咦不是100%吗） 。不能对一个神奇宝贝用多个相同种类的球，但是可以既用宝贝球又用大师球。问最优方案下期望抓到的神奇宝贝数量。 Sol 这题...因为有两个限制，所以要wqs套wqs。 每次二分出 mid1,mid2，表示每使用一个宝贝球就要支付 mid1 的代价，每使用一个大师球就要支付 mid2 的代价，然后正常做dp，记录三个状态：最优方案期望抓多少，最优方案下用多少宝贝球，最优方案下用多少大师球。然后转移取最大值就好了。 一个小细节就是，如果同时用宝贝球和大师球，那期望不仅仅是 pi+qi，而应该是 pi+qi−piqi。这个推一推式子就知道了。 代码 [HEOI2018] 林克卡特树 Description 给定一棵 n 个节点带边权的树，求 k+1 条点不相交的链使得边权和最大。k=k ，那就得记录当前的 mid 了。 https://www.cnblogs.com/YoungNeal/p/10381611.html