重修 Slope Trick(看这篇绝对够!)

2022年05月11日 阅读数:3
这篇文章主要向大家介绍重修 Slope Trick(看这篇绝对够!),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Slope Trick 算法存在十余载了,可是我没有找到多少拍手叫好的讲解 blog,因此凭借本人粗拙的理解来写这篇文章。ios

本文除标明外全部图片均为本人手绘(若丑见谅),画图真的不容易啊 qwq(无耻求赞)。c++

Slope Trick 是啥?

凸代价函数DP优化。算法

具体哪一种题目?

AcWing273. 分级函数

CF713C Sonya and Problem Wihtout a Legendoop

CF13C Sequence优化

P2893 [USACO08FEB]Making the Grade Gspa

P4331 [BalticOI 2004]Sequence 数字序列设计

P4597 序列 sequence3d

P8118 Mysterycode

千万题目汇成一句话:

给定长度为 \(N(\le 10^6)\) 的序列 \(A\),构造一个长度为 \(N\) 的非降序列 \(B\),最小化 \(S=\sum\limits^N_{i=1}|A_i−B_i|\),求出 \(S\) 的最小值和 \(B\) 的构造方案。

注意 Slope Trick 不止可以解决这个问题,这个题目只是便于举例而已。

暴力咋作?

就是 \(O(n^2)\) 的 DP。

\(f_{i,j}\) 表示 \(A\) 中第 \(i\) 个数变为 \(j\),前 \(i\) 个数变为非降序列的最小代价,即

\[\min_{B_1\le B_2\le\dots\le B_i=j}\sum_{k=1}^{i}|A_k−B_k| \]

则有递推式

\[f_{i,j}=|A_i-j|+\min_{k=minV}^{j} f_{i-1,k} \]

其中 \(minV\) 指值域下界。

固然,为了后续的拓展,咱们设

\[g_{i,j}=\min_{k=minV}^{j}f_{i,k} \]

则递推式改为

\[f_{i,j}=|A_i-j|+g_{i-1,j} \]

是否是很是美观?

过渡

在下一步以前,咱们须要几个定义和引理。

引理 A

两个斜率分别为 \(a,b\) 的一次函数相加的斜率为 \(a+b\)

定义 1

咱们称这样的函数为美妙的函数

  • 函数连续。
  • 函数由若干条一次函数(或常数函数)拼接而成(因此是分段函数),且一次函数的斜率为整数。
  • 函数下凸,即若干条一次函数的斜率从左往右单调非减。

引理 B

任意两个美妙的函数相加仍是美妙的函数。

定义 2

设一个连续函数 \(f(x)\)前缀最小函数 \(g(x)\)

\[g(x)=\min_{x'\le x}f(x') \]

引理 C

一个美妙的函数的前缀最小函数仍是美妙的函数,且最后一段(至 \(x\to\infty\))为常数函数。

咋拓展到 Slope Trick?(正题)

先回忆一下递推式

\[f_{i,j}=|A_i-j|+g_{i-1,j} \]

咱们设 \(F_i(x)\) 函数

\[F_i(x)=f_{i,x} \]

相似地

\[G_i(x)=g_{i,x} \]

最后设

\[H_i(x)=|x-A_i| \]

咱们再次改写递推式

\[F_i(x)=H_i(x)+G_{i-1}(x) \]

简洁美观!(请牢记这个公式)

由数学概括法获得 \(F,G,H\) 都是美妙的函数。

咱们维护 \(S_1,S_2,\dots,S_c\)\(G\) 函数的转折点。

来几张图演示一下。

设这个 \(G_i\) 从一次函数到常数函数的转折点为 \(P_i\)

值得注意的是,若一个转折点左边斜率 \(>\) 右边斜率 \(+1\),则这个点是要再重复 \((\) 左边斜率 \(-\) 右边斜率 \(-1)\) 次的,即:

而后加上 \(H_i\),要分类:

\(A_i\ge P_{i-1}\)

这样答案(为最右边水平部分的 \(y\) 坐标)不变,即

\[\begin{aligned} F_i(P_i)&=H_i(P_i)+G_{i-1}(P_i) \\ &=G_{i-1}(P_i) \\ &=G_{i-1}(P_{i-1}) \\ &=F_{i-1}(P_{i-1}) \end{aligned} \]

没有贡献。

并且对于 \(\{S\}\),只用将 \(A_i\) 插入 \(\{S\}\) 末尾便可。

\(A_i<P_{i-1}\)

这样答案为

\[\begin{aligned} F_i(P_i)&=H_i(P_i)+G_{i-1}(P_i) \\ &=P_i-A_i+F_{i-1}(P_i) \\ &=P_i-A_i+F_{i-1}(P_{i-1})+P_{i-1}-P_i \\ &=F_{i-1}(P_{i-1})+P_{i-1}-A_i \end{aligned} \]

即增长

\[F_i(P_i)-F_i(P_{i-1})=P_{i-1}-A_i \]

因此将 \(Ans+\!=P_{i-1}-A_i\)

此时 \(A_i\) 插入 \(\{S\}\)两次,由于他是绝对值函数的转折点,因此两边斜率差值为 \(2\)


相信不少人都蒙了,咱们具象一下。

想象有一条左右无限长的铁丝。

初始化:一开始平放在高度 \(0\) 的位置(\(F_0(x)=G_0(x)=0\)

而后进行 \(n\) 次操做,第 \(i\) 次:

  1. 铁丝横坐标为 \(A_i\) 的地方用尖嘴钳固定住。

  2. 将尖嘴钳左边的部分向上翘 \(1\) 单位的斜率(这部分铁丝每一点都要弯 \(1\) 斜率)。

  3. 尖嘴钳右边的部分同理向上翘 \(1\) 单位的斜率。这样整条铁丝更像「U」形。

这样咱们从 \(G_{i-1}\) 获得了 \(F_i\)

  1. 将右边翘起的部分压平。即在右边找到一个点使得这里的铁丝是水平的(导数为 \(0\))而后从这里往右所有捋成水平的。

这样咱们从 \(F_i\) 获得了 \(G_i\)

  1. 松开尖嘴钳。

最后答案为整个铁丝的最低高度值。

相信前文仔细阅读的小可爱们必定懂了这段扭铁丝具体在对凸函数干吗……


因此用堆维护 \(S_1,S_2,\dots,S_c\) 便可。

总时间 \(O(n\log n)\)

代码?

int n,x,ans=0,b[N];
priority_queue<int> q;
int main(){
	cin>>n;
	For(i,1,n){
		cin>>x;
		q.push(x);
		if(q.top()!=x){
			ans+=q.top()-x;
			q.pop();
			q.push(x);
		}
		b[i]=q.top();
	}
	Rof(i,n-1,1) ckmn(b[i],b[i+1]);
	cout<<ans<<endl;
	For(i,1,n) cout<<b[i]<<" "; cout<<endl;
	return 0;
}

更多?

固然,Slope Trick 不止这种建模和推导。

为了证实这一点,咱们再举一个例子。

题面

题目:abc250_g Stonks

大意:

已知接下来 \(n(\le 2\times 10^5)\) 天的股票价格 \(1\le P_1,P_2,\dots,P_n\le 10^9\)

天天你能够(三选一):

  • 买进一股股票
  • 卖出一股股票
  • 什么也不作

\(n\) 天以后你拥有的股票应为 \(0\)

你最初有足够多的钱,求 \(n\) 天结束后能得到的最大利润。

解答

带悔贪心

咱们能够快速想出一种贪心策略:买入价格最小的股票,在能够赚钱的当天卖出。

显然咱们能够发现,上面的贪心策略是错误的,由于咱们买入的股票能够等到能够赚最多的当天在卖出。

咱们考虑设计一种反悔策略,使全部的贪心状况均可以获得全局最优解。(即设计反悔自动机的反悔策略)

咱们先把当前的价格放入小根堆一次(此次是以上文的贪心策略贪心),判断当前的价格是否比堆顶大,如果比其大,咱们就将差值计入全局最优解,再将当前的价格放入小根堆(此次是反悔操做)。至关于咱们把当前的股票价格若不是最优解,就没有用,最后能够获得全局最优解。

上面的等式即被称为反悔自动机的反悔策略,由于咱们并无反复更新全局最优解,而是经过差值消去中间项的方法快速获得的全局最优解。

Slope Trick

首先咱们考虑最朴素的 \(O(n^2)\) DP 作法:\(f_{i,j}\) 表示前 \(i\) 天过完,如今手上 \(j\) 张股票,所盈利的最大价值。

\[f_{i,j}=\max\{f_{i-1,j+1}+P_i\, ,\, f_{i-1,j}\, ,\, f_{i-1,j-1}-P_i\} \]

而后咱们设函数 \(F_i(x)=f_{i,x}\)(老套路了)。

\[F_i(x)=\max\{F_{i-1}(x+1)+P_i\, ,\, F_{i-1}(x)\, ,\, F_{i-1}(x-1)-P_i\} \]

也就是说将函数 \(F_{i-1}\)

  • 向上 \(P_i\) 单位,向左 \(1\) 单位复制一份,设为 \(F^+_{i-1}\)
  • 向下 \(P_i\) 单位,向右 \(1\) 单位复制一份,设为 \(F^-_{i-1}\)
  • 本身 \(F_{i-1}\) 也保留。

再求三者的上凸包(\(\max\))即为 \(F_i\)

这里引用 Atcoder 官方题解的图:

咱们发现 \(F_{i-1}\) 只有左边斜率 \(>-P_i\) 且右边斜率 \(<-P_i\) 的点才会相对于 \(F_{i-1}^+,F_{i-1}^-\)「露在外面」。

这时会在原本的斜率序列中插入两个斜率为 \(-P_i\) 的线段,同时将原本最靠左的线段去掉。因此用堆维护这个斜率序列,插入两个 \(P_i\),弹出一次堆顶。

固然,若是 \(P_i\) 小于堆顶,则只要插入 \(P_i\) 便可。

代码

两种解法代码同样神奇吧

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define For(i,j,k) for(int i=j;i<=k;i++)
#define int long long
#define N 200010

int n,ans=0,x;
priority_queue<int,vector<int>,greater<int> > q; 
signed main(){IOS;
	cin>>n;
	For(i,1,n){
		cin>>x;
		if(i!=1 && q.top()<x){
			ans+=x-q.top();
			q.pop();
			q.push(x);
		}
		q.push(x);
	}
	cout<<ans<<endl;
return 0;}