slope trick

很多时候 dp 数组可以被我们描述成一个一次分段函数，而这可以加速 dp 的转移。 # 如何描述 维护某个 $x_0$ 处的值 $f(x_0),k_0$ 与所有斜率变化点的集合，具体而言，斜率变化了 $\Delta k$ 就往数据结构中插入 $\Delta k$ 个斜率变化点。 一半而言我们维护不同的凸壳时用不同的集合维护，比如下凸壳集合中只维护 $k < 0$ 的直线并且每个变化点代表斜率增加 $1$，其余情况类似。 # 如何快速操作 1. 将其与另一个一次函数相加：直接将 $f(x_0),k_0$ 相加，并合并斜率变化点集合。 2. 取前缀/后缀 $\min$，取维护 $k < 0$ 或者是 $k > 0$ 的的集合变化点。 3. 平移，维护 $f(x_0),k_0$ 的变换，在全局打平移标记。 剩下的见到了再来写。 # 例题 ## P4331 [BalticOI 2004] Sequence 数字序列 $a_i \gets a_i - i$ 后限制变为不降。 设 $f_{i,j}$ 表示使得 $b_i = j$ 的前提下最小化的代价。 $f_{i,j} = \min_{k \leq j}(f_{i-1,k} + |a_i - j|)$。 设 $F_{i}(j) = f_{i,j}$，转移就是将 $F_i$ 取前缀 $\min$ 后再加一个绝对值函数。 更具体地，这题取前缀 $\min$ 的操作告诉我们只用维护一个下凸壳，也就是每个分界点都代表斜率增加 $1$。 我们维护 $x_0 = \infty$ 时 $f(x_0) = 0,k_0 = 0$，也就是说一个分界点右边的斜率等于集合中在他后面有多少个分界点（对于相同的分界点表示多次斜率变化以插入顺序为第二关键字在集合中排序）取相反数得到。 第一个分段函数为： $F_1(x) = a_i - x (x \leq a_i)$ $F_1(x) = 0 (x > a_i)$。 定义 $end$ 为斜率为 $0$ 的线段的左端点，也就是斜率为 $-1$ 的线段的右端点，也是我们凸包的最后一个分界点，即集合中最大值。 假若新加入的函数为 $g(x) = |a_i - j|$。 假若 $a_i \geq end$，首先 $f(x_0),k_0$ 没有变化，而 $a_i$ 前面的分界点右边的线段斜率减去 $1$，因此将 $a_i$ 插入集合末尾即可。 假若 $a_i < end$，那么 $a_i$ 前面的线段斜率仍然减去 $1$，也就是我们需要把 $a_i$ 插入到最后一个小于 $a_i$ 的分界点后面，对于所有大于等于 $a_i$ 的分界点而言，最后一个分界点右端的斜率变成了 $0$ 而左端的斜率变成了 $1$，这一段 $1$ 的线段是无用的，因此我们把最后一个分界点丢掉，用倒数第二个分界点的右端来表示这条新的斜率为 $0$ 的线段，但是此时因为弹出了最后一个，所以我们插入的 $a_i$ 以及其左边的点在集合中后面的分界点数量减少了 $1$，因此我们需要再次插入一个 $a_i$ 来补足它们的斜率表示。 更新完后答案是 $f_{i,\infty}$ ，考虑如何取维护答案的变化，发现每次弹出 $end$ 时，$end$ 依然是斜率为 $0$ 的线段的右端点，因此此时斜率为 $0$ 的线段的左端点的值增量就等于 $end - a_i$。 考虑如何构造方案，最后一个点的决策肯定是 $f_{i,end}$ 也就是变成 $end$，观察 dp 过程中我们的决策点（分界点）实际上一直在向后移动，因此对于 $i \in [1,n-1]$，这个点的决策假若要转移到最优决策的的话应当满足这个决策尽可能靠后（这样才能保证最后移动到下凸壳末尾也就是点 $n$ 的最优决策处），同时不超过前面一个决策且不掉出下凸壳，因此将 $end$ 与点 $i+1$ 的决策取 $\min$ 即可。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6+114; int a[maxn],n,b[maxn],res; priority_queue<int> q; signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i],a[i]-=i; b[1]=a[1]; q.push(a[1]); for(int i=2;i<=n;i++){ q.push(a[i]); if(q.top()>a[i]){ q.pop(); q.push(a[i]); } b[i]=q.top(); } for(int i=n-1;i>=1;i--) b[i]=min(b[i],b[i+1]); for(int i=1;i<=n;i++) b[i]+=i,a[i]+=i; for(int i=1;i<=n;i++) res+=abs(a[i]-b[i]); cout<<res<<'\n'; for(int i=1;i<=n;i++) cout<<b[i]<<' '; return 0; } ```