wqs二分 学习笔记

wqs二分学习笔记

wqs二分适用题目及理论分析

wqs二分可以用来解决这类题目：

给你一个强制要求，例如必须(n)条白边，或者划分成(n)段之类的，然后让你求出最大（小）值。但是需要满足图像是个凸包。

这里讲一下它的原理。假设我们现在需要解决的问题是求分(x)段的最小花费。我们假设对于每个(x)它的最小花费(f(x))的图像长成这个样子:

当然，这只是个大概图像。

我们假设拿一条斜率为(k)的直线去切它，我们假设切到的截距最大值为(g(k))，使截距最大点为(n)，那么图像大概长成这个样子。

我们显然可以得到一个式子：

[f(n)=kn+g(k) ]

[Rightarrow g(k)=f(n)-kn ]

于是，我们只需要知道(g(k))和(n)就可以求出(f(n))。

我们观察(g(k))的式子，发现其实就等价于每分一段贡献在原有的基础上少(k)（对于这个问题而言），于是我们可以忽略段数限制，直接做( exttt{dp})，就可以找到最小截距和(n)。

我们为了满足恰好分成(x)段的要求，如果我们当前的(n)小了，我们就应该把(k)变小，反之亦凡，于是我们就可以使用二分查找到合适的(k)使得(n=x)从而计算出(f(x))了。（这个应该很显然吧）

（所以谁能告诉我为什么可以不用二分小数啊？？？）

例题讲解

( ext {The 1st})

忘情

题目描述

给你一个有(n)个数的数列，要求你分成(m)段，每一段的贡献为((sum a_i+1)^2),求出最小贡献和。

解题思路

真的很经典（虽然最经典还是Tree I）

如果没有恰好分成(m)段，我们可以轻易地列出( exttt{dp})式，即:

[dp[i]=min_{j=1}^{i-1}{dp[j]+(pre[i]-pre[j]+1)^2} ]

其中(pre[i]=sum_{j=1}^{i} a_j)。

现在有了分成(m)段的条件，我们发现只需要说明这是个凸函数就可以使用( exttt{wqs})二分了。这个感性证明一下就好了。然后使用斜率优化就可以做到(Theta(nlog w))。其中(w)是值域。

( ext {Code})

代码戳这里打开

( ext {The 2ed})

林克卡特树

题目描述

给定一棵(n)个点的数，再给定(k)，求出树上不相交的(k+1)条链的权值最大和。需要注意的是，链是可以在树上拐个弯的。

解题思路

首先很显然这是个上凸函数。于是我们可以考虑使用( exttt{wqs})二分。为了方便，后面设(v)为( exttt{wqs})二分中的斜率。

考虑不考虑段数的(dp)，我们可以设(dp[u][0/1/2])，表示(u)这个点与儿子之间有(0/1/2)条连边时以(u)为根的子树内所包含的链权值之和的最大值。

为了方便，(dp[u][1])是还未构造完当前这条链的权值和，也就是说这个东西不需要减去(v)。

设：

[k=max {dp[v][0],dp[v][1]-v,dp[v][2]} ]

可以得出(dp)式:

[dp[u][2]gets max{dp[u][2]+k,dp[u][1]+dp[v][1]+w-v} ]

[dp[u][1]gets max{dp[u][1]+k,dp[u][0]+dp[v][1]+w} ]

[dp[u][0]gets dp[u][0]+k ]

注意开( ext {long long})即可。

( ext {Code})

代码戳这里打开

( ext {The 3rd})

Gosha is hunting

解题思路

考虑最朴素的(n^3 exttt{dp})，可以设(dp[i][j][k])表示前(i)个神奇宝贝用了(j)个宝贝球和(k)个超级球的最大期望捕捉个数。

容易得到转移式:

[f[i][j][k]=max{f[i-1][j][k],f[i-1][j-1][k]+p[i],f[i-1][j][k-1]+u[i],f[i-1][j-1][k-1]|+p[i]+u[i]-p[i] imes u[i]} ]

我们发现如果我们固定(j)，可以通过打表发现这其实是个凸函数，于是我们可以使用( exttt{wqs})二分做到(Theta(n^2log n))。我们发现对于(j)也有同样的性质，所以我们可以( exttt{wqs})套( exttt{wqs})二分做到(Theta(nlog ^2 n))。

不过似乎概率都是(1)的时候会卡掉，因为它不是一个凸函数函数了，到后面是一个常函数了。但是这道题数据很水，所以还是没有被卡。

( ext {Code})

代码戳这里打开

( ext {The 4th})

题目传送门

题目大意

现在有(n)个村庄，你需要在里面选出(k)个作为邮局，使得每个村庄到其最近的邮局之和最小。

思路

这道题其实跟( ext {The 1st})有些类似。

首先我们可以列出(dp)式，设(dp[i][j])表示前面(i)个村庄选出(j)个作为邮局，那么，容易得到:

[dp[i][j]=min{dp[k][j-1]+ exttt{cost}(k+1,i)} ]

其中( exttt{cost}(i,j))表示(i o j)这段村庄选出一个作为邮局的最小距离和，不难想到选出来的村庄为中间点时最优，于是可以利用前缀和(Theta(1))求出。

那接下来应该怎么办呢？第一种办法就是平行四边形优化，但显然时间复杂度还是(Theta(n^2))，虽然足以通过此题，但是不能满足我们对时间复杂度的渴望。第二种办法就是( exttt {wqs})二分。

感性理解一下，随着选出来的村庄的增多，那么，增长速度也会逐渐变慢。于是可以得到，当前函数为凸函数，也就可以用( exttt {wqs})二分。

那么，我们现在就可以得到(dp)式了:

[dp[i]=min{dp[j]+ exttt{cost}(j+1,i)+ exttt{extra}} ]

其中( exttt {extra})表示额外花费。

我们惊奇地 通过打表 发现，这个东西是具有决策单调性的，于是，我们就可以使用决策单调栈优化了。

综上，时间复杂度为(Theta(nlog ^2n))。

( ext {Code})

代码戳这里打开

( ext{The 5th})

题目传送门

题目大意

给出 (n,k) ， 将一个长度为 (n) 的序列分成 (k) 段，每一段的贡献是矩阵的一个子矩阵的区间和。求出最小划分贡献。

(nle 4000,0le kle min(n,800))

思路

首先不难想到一个 (Theta(n^2k))的dp方法，我们设 (f_{i,j}) 表示前面 (j)分成 (i) 段的最小花费，可以得到转移式：

[f_{i,j}=f_{i-1,k-1}+cost(k,j) ]

其中 (cost(k,j)) 表示左上角为 ((k,k)) 右下角为 ((j,j)) 的子矩阵的和。

然后可以发现这个函数是个凸函数，因为它分得越多它的贡献肯定越小，而且它下降的速率肯定会越来越慢（感性理解），于是我们就可以使用( exttt {wqs})二分了，但是这样直接转移还是 (Theta(n^2log w)) ，其中 (w) 是值域，还不足以通过此题，然后我们通过打表发现决策点单调递增，于是我们就可以使用单调栈了。