决策单调性+斜率优化+wqs二分优化dp

叫我杨同学

2026-05-15 21:48:08

发布于：四川

16阅读

0回复

0点赞

主要是因为网上的 wqs 二分文章有点太难懂了（起码对于我），连带着斜率优化和决策单调性一起讲了，顺便梳理一下这几天的学习。

凸包/斜率优化。

定义凸包：平面上一些点，能将这些点包围起来的最小凸多边形称为凸包。

假设你会凸包。不会的也别急，很好理解的（真的）。

“凸”其实就是间距尽量小的时候的差分数组单调。比如 $y=x^2+3x-2$ 就是凸函数（上凸）， $y=-x^2+3x-2$ 也是凸函数（下凸）， $y=\dfrac{1}{x}(x>0)$ 不是， $y=\dfrac{1}{x}(x<0)$ 是。

不妨变化标准形式（ $A$ 和 $B$ 和 $D$ 都是来自 $i$ 的系数， $C$ 可以理解为转移方程的 $f$ ， $x_j$ 和 $y_j$ 都可以看作和 $j$ 相关的数，可以是任意数，也可以是和 $C$ 相关的）：

$C_i=\min\limits^{r(i)}_{j=l(i)}(A_ix_j+B_iy_j+D_i)=D_i+B_i\min\limits^{r(i)}_{j=l(i)}(\dfrac{A_i}{B_i}x_j+y_j)=D_i+B_i\min\limits^{r(i)}_{j=l(i)}(y_j-(-\dfrac{A_i}{B_i}x_j))$ 。

这玩意是不是像直线解析式？后面的 $\min$ 中就是直线的交点（也就是截距）（ $b=y-kx$ ）。那么每个点可以转换为 $(x_j,y_j)$ ，斜率就是 $-\dfrac{A_i}{B_i}$ 。

由于凸包将所有点都给包起来了，所以最优决策点肯定是在这个凸包的边缘去到。我相信你们是会凸包的。

不同的场景对应不同的实现：

用平衡树维护凸壳．那么寻找决策点的二分操作就转化为在平衡树上二分，插入决策点就转化为在平衡树上插入一个结点，并删除若干个被踢出凸壳的点．此方法思路简洁但实现繁琐（来自 OI-wiki）。此时你可以做任何问题（可以区间查询）。（我不会，见谅 /bq）
使用 CDQ 分治（按时间分治）。先将分治的前半部分的 dp 算出来，再建立凸包，接着对于 $[mid+1..r]$ 的，去二分截距切凸包。二分做法：以上凸壳为例，二分答案，以 $k$ 为斜率经过 $mid$ 点的截距与 $mid-1$ 的截距做差分，判断正负以来判断实在这个峰的哪里。
如果 $x$ 具有单调性，可以直接维护一个单调栈，然后做二分。二分同上。
如果 $x$ 和 $k$ 都有单调性，那么可以维护单调栈，在 3 的基础上可以发现最优点是一直向右边移的，所以可以维护一个指针表示最优取值。

决策单调性只能做到 $\log$ ，但是有的时候可以用特殊的 4 情况，可以做到线性，会在最终的大汇总例题见到。

可以先拿 P3195 玩具装箱练练手（其实这个题的 $k$ 和 $x$ 已经是单调递增的了，可以用 4 写法写写做到线性，也可以用其他的练练手）。代码很简单吧。题解区自认为够了。

wqs 二分。

它可以节约状态数。通常是将 $f(i,j)$ 优化成 $g(j)$ 的，同时复杂度也大大降低（通常是 $O(nm)\to O(n\log V)$ ，这里 $i$ 是 $n$ 量， $j$ 是 $m$ 量）。但是可惜的是他的条件很苛刻。

举个例子：最大多区间和。

给你一个长度为 $n$ 的序列 $a$ ， $a$ 可正可负，你要选出恰好 $m$ 个不相交和包含的区间（这里可以将“恰好”做到“至多”），使得这些区间的数的加和尽量大。（把 $n$ 和 $m$ 看作同阶）（这里由于还没讲决策单调性，将 $O(n \log n \log V)$ 的做法先搁一搁，假设允许 $O(n^2\log V)$ 通过）。

典型的做法： $f(i,j)$ 表示前 $i$ 个数中选取 $j$ 个数后，和的最大值。 $f(i,j)=\max(f(i-1,j),\max_{k}(f(k,j-1)+w(k,i)))$ 。 $w(k,i)=s_i-s_k$ ， $s$ 是前缀和。

定义 $g(i)$ 表示全局选 $i$ 个区间的最大区间和（ $g(j)=\max f(i,j)$ ）。

$g$ 具有凸性。用贪心的方法证明，你选少的区间自然有些大点吃不到，你选多的区间自然有些负数你不得不吃，选的刚刚好才有最大得分。当然 写暴力去暴力枚举看下是否凸，但是不要只找小数据手模，因为可能只是个特例。记住要大胆猜测，论证管他的。

把点 $(i,g(i))$ 放到坐标系上。

$\tiny\text{让我来偷一个图(https://www.luogu.com.cn/article/knpufhxe)}$

为了方便说明，记 $p(i,k)$ 表示过 $i$ 的斜率为 $k$ 的直线，截距为 $p(i,k)$ 。

假设我们知道了经过点 $m$ 的线的 $k$ 和 $p(i,k)$ （斜率和截距），显而易见可以求出 $g(m)$ 。由于 $k$ 任意，不妨找到所有点中某个 $k$ 时 $p(i,k)$ 是最大的（这个为什么能做接下来说）。捋一下，这个时候我们就将问题转换成了这个：

找到一个截距 $k$ ，使得所有点中， $p(m,k)$ 是最大的。

（例如，m=1 时候 k=1.5，m=2 时候 k=0.9）

$\tiny\text{让我再来偷一张图，网址同上}$

由于凸性的定义，斜率单调，那么取到 $p$ 极值的时候 $k$ 也是单调的（例如上上个图，分别是 1.5，0.9，0.4，当然不止一个数）。那么我们就可以二分这个 $k$ ，直到他落到 $m$ 点上！（就像上图一样）

好了，思想铺垫弄完了，咋求这个截距？？？

你将截距公式弄出来： $b_i=y_i-kx_i=g(i)-ki$ 。你会发现这个就相当于是你选 $i$ 个区间后要被惩罚掉 $ki$ 。也就是说每次选一个区间，你将受到 $k$ 的惩罚。

你已经有 $k$ 了，定义 $h(i,j)$ 表示在前 $i$ 个数内，选 $j$ 个区间，每选一个区间你将会受到 $k$ 的惩罚，这样子的最大值。

显然： $h(i,j)=\max(h(i-1,j),-k+\max_u (h(u,j-1)+w(u,i)))$ 。

事实上，你只关心 $\max h(n,j)$ 和取得最值的 $j$ 。同理可得每个 $i$ 只管 $h$ 最大的 $j$ （你贪心地想，你无论选 $2$ 个区间还是 $3$ 个区间，你多选，总是会被惩罚的，与原来不同，永不惩罚。若 $2$ 比 $3$ 还优，选 $3$ 不如选 $2$ ，因为最终只考虑所有 $j$ 的 $h$ 最值）。

那么 $h$ 的最后一维可以去掉（ $h(i)=\max(h(i-1),-k+\max_u(h(u)+w(u,i)))$ ），多记录一个数，表示取得最大值的 $j$ 是哪个 $j$ （因为二分时候要用到）。

这样 $h(n)$ 就是截距最大值了！ $j$ 你只需要像二分同款思路一直改变 $k$ 来逼近直到 $j=m$ 。不具体来说，如果 $j>m$ 咋样咋样， $j\le m$ 咋样咋样。

最终二分内部 chk 需要 $O(n^2)$ ，总复杂度是 $O(n^2 \log V)$ 。配合上决策单调性，他会更强。

这里有个我的实现。来自 P1792 [国家集训队] 种树。

我这里简短的讲一讲，大部分可以自己推。由于是个环，可以做两次 dp，第一次考虑 $1 \sim n-1$ ，第二次考虑 $2 \sim n$ ，相当于 $n$ 或 $1$ 每种，自然保证相邻不会挂。dp 可以自己推推，凸性可以自己感性证明。

我的代码有输出方案数的，并且可以处理多点共线，可以参考下。

#include <iostream>
#define int long long
typedef long long ll;
using namespace std;
const int N=2e5+5;
int a[N],n,m;
struct Node{
	int v,x,ct,fl;
	//最大美观度，种了多少棵树，向前多少步，当前位置是否种树&46行左右所使用的标记
	Node()=default;
	Node(int v,int x,int ct,int fl):v(v),x(x),ct(ct),fl(fl){}
}f[N];
Node add(const Node &a,int x,int y){return Node(a.v+x,a.x+y,a.ct,a.fl);}
Node init(const Node a,int x){return Node(a.v,a.x,a.ct,x);}
Node max(Node a,Node b){
	if (a.v>b.v) return a;
	if (a.v<b.v) return b;
	if (a.x<b.x) swap(a,b);
	if (a.x!=b.x && b.ct){return Node(b.v,b.x,b.ct-1,b.fl);}
	if (a.ct>b.ct) return b;
	return a;
}
bool g[N],ans[N];
Node dp(int l,int r,int k,int mt=0){//mt指的是要向前走多少步（处理共线）
	for (int i=l;i<=r;++i){
		if (i>=l+2) f[i]=init(f[i-2],0);
		else f[i]={0,0,mt,0};
		f[i]=max(f[i],init(add(f[i],a[i]+k,1),1));//先转过来再做决策（a[i]+k是个奖励）
		if (i>=l+1) f[i]=max(f[i],init(f[i-1],0));
		g[i]=f[i].fl;
//		cout<<f[i].fl<<"\n";
	}
	return f[r];
}
Node dp(int k){
	return max(dp(1,n-1,k),dp(2,n,k));
}
void solve(){
	cin >> n >> m;
	for (int i=1;i<=n;++i) cin >> a[i];
	if (m==0){
		cout<<0<<"\n\n";
		return;
	}
	if (n==1 && m==1){
		cout<<a[1]<<"\n";
		cout<<1<<"\n";
		return;
	}
	if (m>n/2){
		cout<<"Error!\n";
		return;
	}
	int l=-1e9,r=1e9,k,mid;//这里 l 和 r 我一般开 -1e9 到 1e9 无顾虑，由于这里全都是整数，所以可以是整数二分，如果你闲麻烦可以写实数的
	while (l<r){
		mid=l+r>>1;
//		cout<<"wefewfwefewfwefef\n";
		if (dp(mid).x>=m) r=mid;
		else l=mid+1;
	}
	cout<<dp(l).v-m*l<<"\n";//减去奖励（这里无论是奖励还是惩罚，本质一样）
	int cnt=dp(l).x-m,
	p=max(init(dp(1,n-1,l,cnt),1),init(dp(2,n,l,cnt),2)).fl;
	dp(p,n+p-2,l,cnt);
	for (int i=n+p-2;i>=p;--i) if (g[i]==1) ans[i]=1,--i;
	for (int i=p;i<=n+p-2;++i) if (ans[i]) cout<<i<<" ";cout<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T=1;
//	cin >> T;
	for (int _=0;_<T;++_) solve();
	cout.flush();
	return 0;
}
//天耀中华，天耀中华
//风雨压不跨，苦难中开花
//祥云飘四方，荣誉传八方

典型例题：https://www.luogu.com.cn/problem/P2619 （不用决策单调性的模板题）。

决策单调性。

注意：此处的“决策”是名词“你从哪里转移过来的 dp”，而不是动词。

那么就可以理解为“你在哪里取得最值”的这个点是单调的。

所有决策单调性都依赖于四边形不等式。先讲四边形不等式。

定义 1：若 $w(i,j)$ 满足四边形不等式，对于任意 $a \le b \le c \le d$ ，满足 $w(a,c)+w(b,d) \le w(a,d)+w(b,c)$ 。

定义 2：任意 $a \le l \le r \le b$ ，满足 $w(l,r) \le w(a,b)$ ，则称 $w$ 满足区间包含单调性。

证明某个 $w$ 满足四边形不等式：

自己画数轴暴力拆（这个通常只解决 $w$ 好表示的）（这个挺常用的，其他的都没见过）。
若 $w_1(i,j)$ 和 $w_2(i,j)$ 都满足四边形不等式/恒等式/区间包含单调性，那么任意 $c_1,c_2 \ge 0$ ， $c_1w_1+c_2w_2$ 满足四边形不等式/恒等式/区间包含单调性。
若存在函数 $f(i)$ 和 $g(i)$ （例如前缀和）使得 $w(i,j)=f(i)-g(i)$ ，那么 $w$ 满足四边形恒等式。若 $f$ 和 $g$ 单调增加、 $w$ 还满足区间包含单调性。
若 $h(x)$ 是个单调递增的凸函数，若 $w(i,j)$ 满足四边形不等式并且对区间包含关系有单调性（可增可减），则 $w_1(i,j)=h(w(i,j))$ 满足四边形不等式和区间包含单调性。
若 $h(x)$ 凸， $w(i,j)$ 满足四边形恒等式和区间包含关系的单调性，那么 $w_1(i,j)=h(w(i,j))$ 满足四边形不等式。
最最最无敌的方法：如果你看某个 $w$ 非常有四边形不等式，但是死活证明不出来，写暴力去暴力枚举几组看下决策点是否单调，但是不要只找小数据手模，因为可能只是个特例。记住要大胆猜测，论证管他的。

接下来我们引入最朴素形式。

$f(i)=\min/\max_j f(j)+w(j+1,i)$ 。

记 $\text{opt}(i)$ 表示 $f(i)$ 取得极值时的 $j$ （决策点）。

这个时候若 $w$ 满足四边形不等式， $\text{opt}$ 单调不下降（超级重要，核心结论）。证明看 OI-WIKI，只需要记住结论就可以了。

写法？这里介绍一种通用的简化 LARSCH 算法（来自 OI-WIKI，非常通用）。

考虑分治， $\text{divide}(l,r)$ 表示求出 $(l..r]$ 的所有 $f$ 值。

定义 $\text{mid}=\lceil\dfrac{l+r}{2}\rceil$ ，假设这个时候 $l$ 和 $r$ 的 $f$ 和 $\text{opt}$ 都已经部分确定了，那么显然 $\text{opt}_l \le \text{opt}_{\text{mid}} \le \text{opt}_r$ 。

那么你就可以枚举决策点（ $\text{opt}_l$ 和 $\text{opt}_r$ 之间），更新 $\text{mid}$ ，然后继续递归分裂子问题。这样既可以动态（就是后面的值依赖于前面的 dp 值，普通的分治没法做）做，也可以避开二分队列那样难写的做法。

代码来自 OI-WIKI。

val_t w(int j, int i);  // 成本函数
val_t f[N];             // 最优值
int opt[N];             // 最小最优决策

// 用决策 j 更新问题 i
void check(int j, int i) {
  if (w(j, i) < f[i]) { // 这篇文章的作者加：此处的 w 可以在内部直接加上 f[j]，这样写还简单一些
    f[i] = w(j, i);
    opt[i] = j;
  }
}

// 递归求解区间 (l, r] 内的问题
void calc(int l, int r) {
  int mid = (l + r + 1) / 2;
  for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);
  if (mid < r) calc(l, mid);
  for (int j = l + 1; j <= mid; ++j) check(j, r);
  if (mid > l) calc(mid, r);
}

// 求解整个区间 [1, n] 内的问题
void solve(int n) {
  // 清空 f 数组
  std::fill(f + 1, f + n + 1, inf);
  // 初始化
  check(1, 1);
  check(1, n);
  // 递归求解区间 (1, n] 内的问题
  calc(1, n);
}

复杂度显然是 $O(n \log n)$ 的，因为每一大层的复杂度总和总是 $O(n)$ ， $O(\log n)$ 层，所以是 $O(n \log n)$ 的。

注意这一行：

for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);

check 的右端点 mid居然不动，左端点居然一直在非常好的 $+1$ 。这启示我们一些需要 $O(n)$ 计算的 $w$ 可以类似莫队一样移动指针。例如 $w(l,r)$ 表示 $[l..r]$ 中每个值的出现次数平方（注意这里是分别平方）的和。

这里比较特殊，可以直接先暴力算出 $[\text{opt}_l..\text{mid}]$ ，然后一个一个往右边走，将左边算过的点删除（比如对于这个例子，可以维护值域数组 v[i] 表示值是 $i$ 数的个数，删除的时候先把原来的贡献减去 ans-=v[i]*v[i]，--v[a[i]]，再加上现在的贡献 ans+=v[i]*v[i]）。还有一种方法就是暴力算出 $[\min(\text{opt}_r,\text{mid})..\text{mid}]$ ，然后再加入。

接下来我们解决形式 2（区间 dp 形式，用的较少）。

形式 2：在一个操场上摆放着一排 $N$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 $2$ 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将 $N$ 堆石子合并成一堆的最小得分。 $N \le 2000$ 。P5569 弱化版。

显然最朴素的方程是 $f(l,r)=\min_k f(l,k)+f(k+1,r)+w(l,r)$ 。

这个时候 $w$ 显然满足四边形不等式和区间包含单调性。所以这个时候有结论（1）： $f$ 满足四边形不等式。

这个时候 $f$ 满足四边形不等式，则有结论（2）： $\text{opt}_{l,r-1} \le \text{opt}_{l,r} \le \text{opt}_{l+1,r}$ 。

那么我们就可以直接枚举决策点区间去做。由于对于每个 $l$ ，遍历的长度总和是 $O(n)$ 的，所以复杂度是 $O(n^2)$ 的。（这个很少用）

好了，决策单调性讲完了，这个时候我们就可以回收 wqs 所留的问题了。把式子拿过来： $h(i)=\max(h(i-1),-k+\max_u(h(u)+w(u,i)))$ 。 $w$ 可是满足四边形恒等式啊！具有决策单调性了啊！做完了（这里不影响 wqs 所需要记录的最优次数），时间复杂度 $O(n \log n)$ ，算上 wqs 二分就是 $O(n \log n \log V)$ ，略逊于反悔贪心。

他和凸性的关系？咱们回到原来 wqs 二分的式子来。 $f(i,j)=\max(f(i-1,j),\max_{k}(f(k,j-1)+w(k,i)))$ 。

这里直接给出结论： $g(j)=\max f(i,j)$ 具有凸性。这个非常有用，返回原来的 wqs 问题，就可以直接证明它有凸性了。还有更多的证明凸性可以见 oi-wiki。

非常感谢：https://oi-wiki.org/dp/opt/quadrangle/

好的，让我们来看一道非常综合的题目！

题目。

题目大意

给定一个 $n$ 个 $\texttt{A}$ 和 $n$ 个 $\texttt B$ 组成的字符串 $S$ ，交换最少对元素使得：

存在一种方式，把 $S$ 划分为 $k$ 个子序列，每个子序列 $\texttt{A},\texttt B$ 数量相等且所有 $\texttt A$ 在所有 $\texttt B$ 左边。

数据范围： $n\le 10^6$ 。（来自 DaiRuiChen007 的题解，https://www.luogu.com.cn/article/amcj6rjb ）

这里的题解都是基于 https://www.luogu.com.cn/article/amcj6rjb 理解的，讲的非常简短，但是有点笔误，代码中 inline array<ll,2> check(ll x) 使用 array 作为返回值，确实强！我这里主要是想讲的清楚一点。

遇见难题，先想想超级暴力咋做，一般是有前途的。

由于是子序列划分，所以普通的“ $f(i,j)$ 表示前 $i$ 个数划分为 $j$ 段，这个状态的最小交换次数”完全不可做（他那个选的东西又不连续），所以考虑其他的。

换一个方面想，假设原序列就有解，先将 A 和 B 匹配，然后再把某些东西组合起来，这样也可以得到答案。

这启发我们将匹配的个数放到状态里。定义 $f(i,j)$ ，表示将前 $i$ 个 A 和 B 安排到了前 $j$ 个乐曲，这样的最小交换次数。（后面我相信读者可以自己推出来）

这个时候也就有了一个非常好的性质：同一个乐曲中，选出来的 A 的次第是个区间。这个也很好证，如果不是个区间，反而不优（可以通过举例法或感性理解来猜到这个结论）。这里给个感性证明：你想咋选咋选，反正“区间”这一选法是一定存在在最优集合里面的。

这个就刚好解决了选点不连续的问题，那么 $f(i,j)=\min\limits^{i-1}_{k=0}f(k,j-1)+w(k+1,i)$ 。 $w(l,r)$ 表示将第 $[l..r]$ 个 A 和第 $[l..r]$ 个 B 安排成一个合法的队伍需要的最少次数。

设 $p_i$ 表示第 $i$ 个 A 前面有多少个 B，那么 $w(l,r)=\sum\limits^{r}_{i=l}\max(0,p_i-l+1)$ 。解释：这里是要将多少个 B 换到后面才有戏。

这个四边形不等式能证明（见后面），但是可以通过打表来证明。这个凸性也就证明出来了。由于 $w$ 满足四边形不等式，所以 $g(i)$ 具有凸性。

这里我们选择 wqs 二分。这样是 $O(n \log n \log V)$ 的，但是此题 $n \le 10^6$ 。但是恭喜你获得了 $87$ 分！所以考虑更优的做法。

考虑将 $w$ 优化。这个 $w$ 拆开就是个 $s$ （前缀和）和 $q$ （这里 $q_x$ 指的是第一个 $i$ 使得 $p_i \ge x$ 的 $i$ ）的表示了，你拆开就可以了。

这里由于 $p$ 有决策单调性（？）所以你算 $q_i$ 的时候可以直接找到 $q_{i-1}$ 然后再往后遍历。这样是 $O(n)$ 的。这样处理比较舒服。

把上面的 $w$ 的式子拿过来， $w(l,r)=\sum\limits^{r}_{i=l}\max(0,p_i-l+1)$ 。那么 $w(l,r)=\sum\limits^{r}_{i=p_{l-1}}(p_i-l+1)=s_r-s_{p_{l-1}-1}-(r-p_{l-1}+1)\times(l-1)$ （这里 $s_i=\sum\limits^{i}_{j=1}p_i$ ）。

这里来证明四边形不等式：首先 $s$ 抵消，然后你把位拆开，发现两项（两个乘法）中都是左边小于等于右边的（遇到这种题，大胆猜结论，如果你想在考场上证明，因为拆式子过于费劲，那耗费的时间足够重新写一份了）。

那么 $g(i)=\min_j g(j)+w(j+1,i)=\min_j g(j-1)+w(j,i)=\min_j (g(j-1)+s_i-s_{p_{j}-1}-(i-p_{j}+1)\times j)=\min_j ((g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)+s_i+i\times j)$ （这里告诉一个非常好的公式换元方法：直接在小熊猫使用ctrl+f替换模式）（g 是 wqs 用）。

具体地（让我们来复习凸包！），当式子满足了这个标准形式： $f(i)=\max _j y_j-k_ix_j$ 就可以进行斜率优化（这里的 max 是 min 也可以）。这个时候 $f(i)$ 就相当于这条斜线的 b 值。

回到原来， $g(i)=s_i+\min_j ((g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)+i\times j)$ 。这个时候令 $y_j=(g(j-1)-s_{p_{j}-1}+p_{j}\times j+j)$ ， $x_j=j$ ， $k_i=-i$ ，就可以做了。此时，显然， $k$ 满足单调递减， $x$ 满足单调递增，所以可以考虑一下直接拿单调栈来实现 $O(n)$ 做 dp。