slope trick/arc123d

通过 arc123D 讨论一下 \(\texttt{slope trick}\)。

part -1

\(\text{slope trick}\) 顾名思义，并不是斜率优化 dp。

part 0

我并没有对 \(\text{slope trick}\) 很深入的理解不具体介绍，只是讲一下 arc123D 的优化技巧。

待填坑。

---

arc123D

link

考虑 \(B,C\) 两个序列不好一起维护，而且 \(B_i+C_i=A_i\)，所以直接只维护一个 \(B\)。

那么 \(B_i\leq B_{i+1}\) 且 \(C_i=A_i-B_i\geq C_{i+1}=A_{i+1}-B_{i+1}\).

所以 \(B_i\leq B_{i+1},B_{i}\leq B_{i+1}-(A_{i+1}-A_{i})\).

设 \(B_i\leq B_{i+1}-D_{i+1}\)。

那么我们可以进行dp。

\(\text{dp}_n(x)\) 表示 \(B_n=x\) 最小答案。

枚举上一个显然有转移：

\[\text{dp}_{n}(x)=\min _{j\leq x-D_{n}}\text{dp}_{n-1}(j)+\mid x\mid+\mid A_n-x\mid\]

发现这本质上是一个前缀最小，加上一个下凸函数 \(\mid x\mid+\mid A_n-x\mid\)。

所以 \(\text{dp}_n(x)\) 的函数图像也为下凸。

关键的来了每次加上的 \(\mid x\mid+\mid A_n-x\mid\) 的斜率仅仅为 \(2\)。

这给我们提供了一个有利条件，最终函数图像是下凸，函数图像被一些整点分割成一段段直线，分割点个数级别是 \(n\) 的。

考虑每一次转移可以被拆分成：平移x坐标，推平最后斜率大于0的，转移即添加4个斜率变化关键点（考虑斜率为2，保证斜率连续）。

具体实现注意，\(x\) 坐标和 \(slope\) 都是单调的，所以只需要维护 \(x\) 坐标即可，剩下的就是一个全局加，单点插入的经典题。

答案即为最后函数 \(slope=0\) 的那段函数值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1000;
int a[N],n;
const int inf=1e10;
priority_queue<int> q;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int lv=0,ls=0,add=0;
    for(int i=1;i<=n;i++){
        int pre=-inf;
        ls=2;
        while(!q.empty()&&ls>0) {
            if(pre!=-inf){
                lv-=(pre-q.top())*ls;
            }
            pre=q.top();
            ls--;q.pop();
        }
        if(i>1) add+=max(0ll,a[i]-a[i-1]);
        int x1=-add,x2=a[i]-add;
        q.push(x1),q.push(x1);
        q.push(x2),q.push(x2);
        int x=q.top()+add;
        lv=lv+abs(x)+abs(x-a[i]);
    }    
    int pre=-inf;
    ls=2;
    while(!q.empty()&&ls>0) {
        if(pre!=-inf){
            lv-=(pre-q.top())*ls;
        }
       pre=q.top();
        ls--;q.pop();
    }
    cout<<lv;
}

---

回看这篇题解，实际上感觉还是很有误导性的。。。

这里说一下我现在对 slope trick 的理解。

凸性的推导

这样的 dp 方程我们不是很能一眼看出凸性，甚至只看方程不看初值的情况下，有的根本没凸性。

所以关于凸性的推到，应该从初值看起，然后用类似数学归纳的方法总结。

主要就是凸函数+凸函数结果还是凸函数，在这里凸函数是斜率不增/不降的分段函数。

维护的大体方式

我们记录这个分段函数断点，规定每一段斜率改变值为 1，同时维护一端的函数（最右端，最左端）（\(kx+b\)）。

我们对斜率是 小正整数要求是硬性的，因为只有这样才能容易维护关键点集合。