Slope Trick学习笔记

洛谷P4597 序列 sequence这题是 CF13C 的数据加强版。题面大意给定一个序列每次操作可以把某个数 1 或 −1。求把序列变成非降数列的最小操作次数n ≤ 5 × 10 5 n\leq 5\times 10^5n≤5×105。题解看到题面不难想到一个非常劣的朴素 dp 无论如何我们先把能想到的东西写出来设d p [ i ] [ j ] dp[i][j]dp[i][j]为到第i ii个数第i ii个数的值是j jj的最小操作次数。d p [ i ] [ j ] min ⁡ 0 ≤ k ≤ j d p [ i − 1 ] [ k ] ∣ a i − j ∣ dp[i][j]\min_{0\leq k\leq j}dp[i-1][k]|a_i-j|dp[i][j]0≤k≤jmin​dp[i−1][k]∣ai​−j∣考虑优化对于每一层i ii把j jj当做x xx轴设函数F i ( j ) min ⁡ 0 ≤ k ≤ j d p [ i − 1 ] [ k ] , G ( j ) ∣ a i − j ∣ F_i(j)\min_{0\leq k\leq j}dp[i-1][k],G(j)|a_i-j|Fi​(j)min0≤k≤j​dp[i−1][k],G(j)∣ai​−j∣。当i 1 i1i1时显然有F 1 ( j ) 0 F_1(j)0F1​(j)0。引理凸性相同的几个分段线性函数的每个点函数值加和后的新函数仍然是分段线性函数且凸性不变。对本题G ( j ) G(j)G(j)是个绝对值函数的特殊情况很容易通过分类讨论归纳证明。而一般性情况对于 oier 来说这种引理是不必要去理解证明的所以请自行搜索。显然∣ a i − j ∣ |a_i-j|∣ai​−j∣是个下凸的分段线性函数因此我们可以知道对于每一层i ii的 dp 值都是下凸的而取 min 操作会使得F ( j ) F(j)F(j)​ 右半部分被拉平。∣ a i − j ∣ |a_i-j|∣ai​−j∣的加入会使新函数里a i a_iai​左边的线段斜率全部 -1右边的斜率全部1。又可以注意到函数内相邻的两段线段的斜率不会差很大因为∣ a i − j ∣ |a_i-j|∣ai​−j∣的加入最多只会使斜率变化 1。所以有个很聪明的办法我们不存线段而是存斜率 1 或 -1 的点只要我们知道什么地方斜率是 0 以及它的函数值因为 dp 取凸包的最值肯定从斜率为 0 取我们就可以维护整个凸包了。举个栗子F ( x ) { − 3 x 9 { 0 ≤ x ≤ 2 } y 1 { 4 ≤ x } − x 5 { 2 ≤ x ≤ 4 } F(x)\begin{cases} -3x9\ \left\{0\le x\le2\right\}\\ y1\left\{4\le x\right\}\\ -x5\left\{2\le x\le4\right\} \end{cases}F(x)⎩⎨⎧​−3x9{0≤x≤2}y1{4≤x}−x5{2≤x≤4}​那么我们要维护的点集就是{ 2 , 2 , 4 } , F ( 4 ) 1 \{2,2,4\},F(4)1{2,2,4},F(4)1​。设函数斜率为0 00直线左端点横坐标为t tt。由于这个下凸单调不升的函数的t tt肯定是点集里x坐标最大的我们就可以用大根堆维护点集。这时候加入一个∣ a i − j ∣ |a_i-j|∣ai​−j∣如果a i ≥ t a_i\geq tai​≥ta i a_iai​左边斜率全 -1即插入一个新点t ′ a i ta_it′ai​F ( t ) F(t)F(t)不变。如果a i t a_itai​t同样加入点a i a_iai​以表示左边斜率-1那么斜率为0的部分就会被抬高斜率1而被舍弃所以弹出大根堆堆顶t不在作为斜率拐点而是新最小值的一部分。且对于新的t ′ tt′有F i ( t ′ ) F i − 1 ( t ) t − a i F_i(t)F_{i-1}(t)t-a_iFi​(t′)Fi−1​(t)t−ai​。code#include bits/stdc.h #define int int64_t //#define int __int128 //#define MOD (1000000007) //#define eps (1e-6) #define endl \n #define debug_endl coutendl; #define debug coutdebugendl; using namespace std; int n,ans; priority_queueint q; signed main(){ //freopen(.in,r,stdin); //freopen(.out,w,stdout); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cinn; for(int i1;in;i){ int x; cinx; q.emplace(x);//无论如何ai的斜率-1 if(!q.empty()xq.top()){ ansq.top()-x;//F_{i}(t)F_{i-1}(t)t-a_i q.pop();//舍弃掉最右侧斜率拐点它不再是了 q.emplace(x);//右侧斜率全体1 } } coutans; return 0; }P4331 [BalticOI 2004] Sequence (Day1)这个题跟上面的题是一样的不过你需要一个小 trick 把严格小于变成小于等于。如果a i a i 1 a_ia_{i1}ai​ai1​则a i 1 ≤ a i 1 a_i1\leq a_{i1}ai​1≤ai1​又注意到i 1 − i 1 i1-i1i1−i1所以a i − i ≤ a i 1 − ( i 1 ) a_i-i\leq a_{i1}-(i1)ai​−i≤ai1​−(i1)。如果是一般的 dp我们就会把每个 dp 值都存一下它从哪里转移假设从k kk转移来d p [ i ] [ j ] d p [ i − 1 ] [ k ] ∣ a i − j ∣ p r e [ i ] [ j ] ( i − 1 , k ) dp[i][j]dp[i-1][k]|a_i-j|\\ pre[i][j](i-1,k)dp[i][j]dp[i−1][k]∣ai​−j∣pre[i][j](i−1,k)在 slope trick 里我们只关心极值点。仍然是那两种讨论我们可以知道如果a i t a_itai​t那么我们是从t tt转移而来应该记录大根堆堆顶如果a i t a_itai​t在 dp 意义下其实是从t ′ tt′自己转移到t ′ tt′所以记录每次的堆顶并从后往前取 min 即可。code#include bits/stdc.h #define int int64_t //#define int __int128 //#define MOD (1000000007) //#define eps (1e-6) #define endl \n #define debug_endl coutendl; #define debug coutdebugendl; using namespace std; int n,ans,a[1000010]; priority_queueint q; signed main(){ //freopen(.in,r,stdin); //freopen(.out,w,stdout); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n; cinn; for(int i1;in;i){ int x; cinx; x-i; q.emplace(x); if(!q.empty()xq.top()){ ansq.top()-x; q.pop(); q.emplace(x); } a[i]q.top(); } coutansendl; for(int in-1;i1;--i){ a[i]min(a[i1],a[i]); } for(int i1;in;i){ couta[i]iendl; } return 0; }还有两个例题没写未完待续……