wqs二分 学习笔记
wqs二分学习笔记
wqs二分适用题目及理论分析
wqs二分可以用来解决这类题目:
给你一个强制要求,例如必须\(n\)条白边,或者划分成\(n\)段之类的,然后让你求出最大(小)值。但是需要满足图像是个凸包。
这里讲一下它的原理。假设我们现在需要解决的问题是求分\(x\)段的最小花费。我们假设对于每个\(x\)它的最小花费\(f(x)\)的图像长成这个样子:
当然,这只是个大概图像。
我们假设拿一条斜率为\(k\)的直线去切它,我们假设切到的截距最大值为\(g(k)\),使截距最大点为\(n\),那么图像大概长成这个样子。
我们显然可以得到一个式子:
\]
\]
于是,我们只需要知道\(g(k)\)和\(n\)就可以求出\(f(n)\)。
我们观察\(g(k)\)的式子,发现其实就等价于每分一段贡献在原有的基础上少\(k\)(对于这个问题而言),于是我们可以忽略段数限制,直接做\(\texttt{dp}\),就可以找到最小截距和\(n\)。
我们为了满足恰好分成\(x\)段的要求,如果我们当前的\(n\)小了,我们就应该把\(k\)变小,反之亦凡,于是我们就可以使用二分查找到合适的\(k\)使得\(n=x\)从而计算出\(f(x)\)了。(这个应该很显然吧)
(所以谁能告诉我为什么可以不用二分小数啊???)
例题讲解
\(\text {The 1st}\)
题目描述
给你一个有\(n\)个数的数列,要求你分成\(m\)段,每一段的贡献为\((\sum a_i+1)^2\),求出最小贡献和。
解题思路
真的很经典(虽然最经典还是Tree I)
如果没有恰好分成\(m\)段,我们可以轻易地列出\(\texttt{dp}\)式,即:
\]
其中\(pre[i]=\sum_{j=1}^{i} a_j\)。
现在有了分成\(m\)段的条件,我们发现只需要说明这是个凸函数就可以使用\(\texttt{wqs}\)二分了。这个感性证明一下就好了。然后使用斜率优化就可以做到\(\Theta(n\log w)\)。其中\(w\)是值域。
\(\text {Code}\)
\(\text {The 2ed}\)
题目描述
给定一棵\(n\)个点的数,再给定\(k\),求出树上不相交的\(k+1\)条链的权值最大和。需要注意的是,链是可以在树上拐个弯的。
解题思路
首先很显然这是个上凸函数。于是我们可以考虑使用\(\texttt{wqs}\)二分。为了方便,后面设\(v\)为\(\texttt{wqs}\)二分中的斜率。
考虑不考虑段数的\(dp\),我们可以设\(dp[u][0/1/2]\),表示\(u\)这个点与儿子之间有\(0/1/2\)条连边时以\(u\)为根的子树内所包含的链权值之和的最大值。
为了方便,\(dp[u][1]\)是还未构造完当前这条链的权值和,也就是说这个东西不需要减去\(v\)。
设:
\]
可以得出\(dp\)式:
\]
\]
\]
注意开\(\text {long long}\)即可。
\(\text {Code}\)
\(\text {The 3rd}\)
解题思路
考虑最朴素的\(n^3\texttt{dp}\),可以设\(dp[i][j][k]\)表示前\(i\)个神奇宝贝用了\(j\)个宝贝球和\(k\)个超级球的最大期望捕捉个数。
容易得到转移式:
\]
我们发现如果我们固定\(j\),可以通过打表发现这其实是个凸函数,于是我们可以使用\(\texttt{wqs}\)二分做到\(\Theta(n^2\log n)\)。我们发现对于\(j\)也有同样的性质,所以我们可以\(\texttt{wqs}\)套\(\texttt{wqs}\)二分做到\(\Theta(n\log ^2 n)\)。
不过似乎概率都是\(1\)的时候会卡掉,因为它不是一个凸函数函数了,到后面是一个常函数了。但是这道题数据很水,所以还是没有被卡。
\(\text {Code}\)
\(\text {The 4th}\)
题目大意
现在有\(n\)个村庄,你需要在里面选出\(k\)个作为邮局,使得每个村庄到其最近的邮局之和最小。
思路
这道题其实跟\(\text {The 1st}\)有些类似。
首先我们可以列出\(dp\)式,设\(dp[i][j]\)表示前面\(i\)个村庄选出\(j\)个作为邮局,那么,容易得到:
\]
其中\(\texttt{cost}(i,j)\)表示\(i\to j\)这段村庄选出一个作为邮局的最小距离和,不难想到选出来的村庄为中间点时最优,于是可以利用前缀和\(\Theta(1)\)求出。
那接下来应该怎么办呢?第一种办法就是平行四边形优化,但显然时间复杂度还是\(\Theta(n^2)\),虽然足以通过此题,但是不能满足我们对时间复杂度的渴望。第二种办法就是\(\texttt {wqs}\)二分。
感性理解一下,随着选出来的村庄的增多,那么,增长速度也会逐渐变慢。于是可以得到,当前函数为凸函数,也就可以用\(\texttt {wqs}\)二分。
那么,我们现在就可以得到\(dp\)式了:
\]
其中\(\texttt {extra}\)表示额外花费。
我们惊奇地 通过打表 发现,这个东西是具有决策单调性的,于是,我们就可以使用决策单调栈优化了。
综上,时间复杂度为\(\Theta(n\log ^2n)\)。
\(\text {Code}\)
\(\text{The 5th}\)
题目大意
给出 \(n,k\) , 将一个长度为 \(n\) 的序列分成 \(k\) 段,每一段的贡献是矩阵的一个子矩阵的区间和。求出最小划分贡献。
\(n\le 4000,0\le k\le \min(n,800)\)
思路
首先不难想到一个 \(\Theta(n^2k)\)的dp方法,我们设 \(f_{i,j}\) 表示前面 \(j\)分成 \(i\) 段的最小花费,可以得到转移式:
\]
其中 \(cost(k,j)\) 表示左上角为 \((k,k)\) 右下角为 \((j,j)\) 的子矩阵的和。
然后可以发现这个函数是个凸函数,因为它分得越多它的贡献肯定越小,而且它下降的速率肯定会越来越慢(感性理解),于是我们就可以使用\(\texttt {wqs}\)二分了,但是这样直接转移还是 \(\Theta(n^2\log w)\) ,其中 \(w\) 是值域,还不足以通过此题,然后我们通过打表发现决策点单调递增,于是我们就可以使用单调栈了。
最新文章
- vim 基本使用
- 如何让你的JavaScript代码更加语义化
- html/css小练习3
- 2017 年值得一瞥的 JavaScript 相关技术趋势
- [转] This Android SDK requires Android Developer Toolkit version 23.0.0 or above
- 随机数生成器console
- myEclipse
- 模板引擎freemarker的简单使用教程
- QCheckBox 的按钮响应
- 2016年11月28日 星期一 --出埃及记 Exodus 20:19
- SqlSever基础 两个条件 group by 分组显示
- 关于dllimport的使用
- Creating a web application.
- 解決 IE10 浏览器无法使用 ASP.NET From 验证登录的问题
- Android bitmap序列化
- CloudFormation
- POJ 1208 The Blocks Problem --vector
- AET 本征半导体
- 日期控件My97 DatePicker 的使用
- Zabbix应用六:Zabbix监控Redis