省选-动态规划-wqs 二分

主要的思想就是 $f(x)$ 关于 $x$ 的图像的斜率单调。

然后这个图像我们是不能在限定的时间内求出来的，只能对于一些点求出其对应的值。

P5633 最小度限制生成树

P5633 最小度限制生成树。

通过这道题来讲一下。

$f(x)$ 表示 $s$ 连接了 $x$ 条边的答案。然后我们发现 $f$ 斜率单调。

我们先求出 MST 时候的 $f$，是最小值，然后向 $x$ 方向一步一步移动。我们用带权二分，二分一个偏移量，就是连接 $s$ 边的权值全部加上一个值（可以为负）以控制连接 $s$ 边的数量。

这也就相当于二分切线的斜率，截距 $b=f(x)−cx$，$c$ 表示偏移量。

因为 $-cx$，所以我们可以画一条线，斜率为 $c$，在原图上放着就行了。我们需要使得当前的 $x$ 为凸包上的顶点，也就是最优的。

看上去这就是两种理解方法。

P2619 [国家集训队] Tree I

P2619 [国家集训队] Tree I。

这道题我们考虑求最小生成树。但是我们发现，我们很难控制白边的数量，所以我们需要对最小生成树加权。就是比如我们白边少了，就需要将黑边的权值提升，让我们尽可能选择白边。

我们发现这个权值就是我们 WQS 二分的那个斜率，我们需要找到能控制到切点为 $need$ 的斜率，二分就行了。

注意边权相同的话按照颜色排序。然后题目保证有解，所以出现二分出来 $hv!=mid$ 的情况一定会出现黑边边权和白边边权相等（当 mid 整数变化导致白边数从 $>need$ 跳到 $<need$ 时，必然存在一些白边和黑边在调整后权值相等，否则不会发生跳跃），直接 $ans=sum-mid\times need$ 就行了。

CF739E Gosha is hunting

CF739E Gosha is hunting。

利用 WQS 二分降维，降低复杂度。

$f_{i,j,k}$ 表示到了 $i$，用了 $j$ 个精灵球 $j$ 个高级球。

$f_{i,j,k}=\max\{f_{i,j-1,k}+p_i,f_{i,j,k-1}+q_i,f_{i,j-1,k-1}+q_i+q_j-q_i\times q_j\}$

可以发现 $i,j$ 固定的时候图像是上凹的，因为用得很密集就代表会有很多 $-p_i\times q_i$。

然后...我们想知道 $x=b$ 的时候的值，WQS 二分可以解决。我们需要求出 $f_{n,a,b}$ 需要对高级球进行加权然后 $dp$ 出来就行了。

其实这道题两个 WQS 套在一起复杂度更优，但一个也能过。

P5896 [IOI 2016] aliens

P5896 [IOI 2016] aliens。

这道题看上去就像 dp，先推一下式子。

我们发现如果一个正方形能够覆盖这个兴趣点，难么，需要经过的对角线上的点就是 $\min(r_i,c_i),\cdots,\max(r_i,c_i)$，然后问题就转化成了选择 $k$ 条线段，需要能够覆盖给定的所有线段，所以我们就把这个二维的问题转化成了一维。

设 $f_{i,j}$ 表示到了 $i$，用了 $j$ 个区间，然后设 $l_i,r_i$ 表示下需要覆盖的区间。

$f_{i,j}=f_{k,j-1}+(r_i-l_{k+1}+1)^2-[r_k\ge l_{k+1}]\times (r_k-l_{k+1}+1)^2$

这让我们想到了斜率优化 dp。令 $g_k$ 表示 $[r_k\ge l_{k+1}]\times (r_k-l_{k+1}+1)^2$

$f_{i,j}=f_{k,j-1}+(r_i-l_{k+1}+1)^2-g_k$

所以这个函数可以用斜率优化来解决。

至于选择区间数那个维度，感性理解：答案关于区间数的函数是一个凹函数，所以我们可以 wqs 二分。

根据这个，斜率优化就可以直接忽略掉第二维了。

$$f_i=f_j+(r_i-l_{j+1}+1)^2-g_j-Mid$$

让所有 $r_i$ 都加上 $1$。

$$(f_j-l_{j+1}^2-g_j-Mid)=(2r_i)l_{j+1}+(f_i-r_i)^2$$

我们按照 $r_i$ 排序，斜率单调，然后就可以做了。这个二分不需要用 double 算，因为 $f$ 是整数。