斜率优化初步

Imakf · 2019-07-19 16:38:18 · 个人记录

怎么说我还是菜，现在还不会这东西，真丢脸

~~我看你是完全不懂哦~~

Part 1 基于单调性的线性做法

例题一、P3195 [HNOI2008]玩具装箱TOY

这题目转移很明显

dp[i]=\min\limits _{j=0}^{i-1} dp[j]+(i-(j-1)+S[i]-S[j]-L)^2

行8，整理一下好看点

dp[i]=\min\limits _{j=0}^{i-1} dp[j]+(S[i]+i-S[j]-j-L-1)^2

设a[i]=S[i]+i,b[i]=S[i]+i+L+1，可简化上式

dp[i]=\min\limits _{j=0}^{i-1} dp[j]+(a[i]-b[j])^2

斜率优化之思想

我们现在考虑到 i 时的转移，如果一个决策点 j_2 比 j_1 (j_1<j_2)更优会怎样？

或者说会有什么特殊的代数关系么？

dp[j_1]+(a[i]-b[j_1])^2>dp[j_2]+(a[i]-b[j_2])^2

dp[j_1]+a[i]^2-2a[i]b[j_1]+b[j_1]^2>dp[j_2]+a[i]^2-2a[i]b[j_2]+b[j_2]^2

dp[j_1]-2a[i]b[j_1]+b[j_1]^2 >dp[j_2]-2a[i]b[j_2]+b[j_2]^2

我们现在只知道a[],b[]两个数组，考虑到b[]带有平方，不如把a[]单独拆出来

好吧实际上我们采用的策略是把带 i 项全部塞到一遍就好了

2a[i]b[j_2]-2a[i]b[j_1]>dp[j_2]-dp[j_1]+b[j_2]^2-b[j_1]^2

2a[i]>\dfrac{dp[j_2]+b[j_2]^2-dp[j_1]-b[j_1]^2}{b[j_2]-b[j_1]}

赶脚没问题了，我们知道斜率是k = \dfrac{\Delta y}{\Delta x}

右边那个式子长得也很像（好吧其实就是）

不如令y_i=dp[i]+b[i]^2 ,x_i=b[i]

每一个决策点都可以对应到一个点(b[i],dp[i]+b[i]^2)

同时根据我们推出来的那个柿子

一旦 k <2a[i] 那就说明这个 j_2 转移更优秀

另外一个性质：见下图

如果决策 j_2 在 j_1j_3 上方，那么必然 j_2 不会成为最优转移

Why?

一旦 k <2a[i] 那就说明这个 j_2 转移更优秀

同时说明一旦 k >2a[i] 那就说明这个 j_2 转移更差

此时已知三条图中线段斜率大小相对关系：

k_{j_2j_3}<k_{j_1j_3}<k_{j_1j_2}

从左到右四个位置，枚举一下 2a[i] 与这三的大小关系

会得到最优分别是:j_1,j_1,j_3,j_3

也就是说无论如何都轮不到 j_2 转移

所以我们维护的可用决策点实际上组成一个下凸壳（因为在上面的转移都更差），斜率单调不减（相邻的斜率可以相等！！！）

其实这还基于另一个事实：

因为那个k<2a[i]，2a[i]是个跟前缀和有关的柿子，是单调递增的，而这个 k 要么是每次都变大，要么是不变。

这就有一个更重要的性质：若决策点 s 在第 i 次决策被发现差于决策点 t，那么此后的决策中 s 永远不可能优于 t.

因为斜率的限制是越来越放宽的。

斜率优化之实现

思想我们已经清楚：维护一个决策点凸包，每次找到最优决策点，直接转移。

问题是我们怎么维护凸包，怎么找最优决策点。

所以我们需要用两个到上文的性质

1

若决策点 s 在第 i 次决策被发现差于决策点 t，那么此后的决策中 s 永远不可能优于 t.

说实话，凸包有点像单调队列不是吗？

当一个决策点又比你小又比你强，你就可以退役了。

所以活下来的都是比强者菜一点点的年轻 oier。

当我们完成了 i 的转移，需要把 i 插入队列末尾

我们就要把比它大，又比它菜的转移点弹出。

~~老年退役选手~~

具体操作方式就是按照之前那张图来。

2

但维护凸包的过程也不完全是单调队列。

我们把凸包最左下的决策点当成老年强者。

按照我们先前的式子

一旦 k <2a[i] 那就说明这个 j_2 转移更优秀

因为 2a[i] 的限制是不断放宽的

所以 j_1 也许有一天就被次优决策 j_2 超过了

长江后浪推前浪，浮事新人换旧人。

具体操作方式就是每次转移前检查 front 是否被超越

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>

#define rg register
#define il inline
#define MX (50000 + 5)
#define ll long long
#define db double   

ll S[MX] ,dp[MX] ,a[MX] ,b[MX] ,Q[MX];
il double slope(int j1 ,int j2){
    return (db)(dp[j2] + b[j2] * b[j2] - dp[j1] - b[j1] * b[j1]) / (b[j2] - b[j1]);
}

int main(){
    int n ,l;
    scanf("%d%d" ,&n ,&l);
    for(rg int i = 1 ,tmp ; i <= n ; ++i){
        scanf("%d" ,&tmp);
        S[i] = S[i - 1] + tmp;
        a[i] = S[i] + i;
        b[i] = S[i] + i + l + 1;
    }
    b[0] = (l + 1); 
    int head = 0 ,tail = 0; //从0开始
    //Q[0] = 0;
    for(rg int i = 1 ; i <= n ; ++i){
        while(head < tail && slope(Q[head] ,Q[head + 1]) < 2 * a[i])    ++head;
        // 检查 front 是否是最优
        dp[i] = dp[Q[head]] + (a[i] - b[Q[head]]) * (a[i] - b[Q[head]]);
        while(head < tail && slope(Q[tail] ,i) < slope(Q[tail - 1] ,Q[tail]))   --tail;
        // 尾部插入，单调队列
        Q[++tail] = i;
    }
    printf("%lld\n" ,dp[n]);
    return 0;
}

论斜率优化的另一种推柿子方法

上文方法在某些题目中会受限。

例如斜率不单调、正负性不确定。

所以留坑

例题二、[USACO08MAR]土地征用Land Acquisition

~~按理来说这题应该更用来做例题~~

先考虑贪心，把无用的土地（比另一块土地x,y都小）除掉

具体怎么做？排序，按 x 为第一关键字从小到大 , y 为第二关键字从小到大排序

我们已经保证 x 全体有序，只需记录当前 y 值最大，比 y_{max} 小的都不需要了

此时盲猜一个结论，必须一段一段的买才会最优。

假设此时只有三块土地，已经排好序。

三块一起买就是 x[1]\times y[3]

打乱顺序先买 1,3 ，单买 2 就是 x[1]\times y[3]+x[2]\times y[3]

显然一起买更优，我们可以通过数学归纳法推广到任意情况。

于是可以直接写出方程 dp[i]=\min \limits^{i -1}_{j=0} dp[j]+x[j+1]y[i]

显然是一个斜率优化的方程（而且比较裸）

令 j_!<j_2 且 j_2 转移更优则有

dp[j_2]+x[j_2+1]y[i]<dp[j_1]+x[j_1+1]y[i]

(x[j_2+1]-x[j_1+1])y[i]<dp[j_1]-dp[j_2]

因为我们已经排过序，所以保证x[j_2+1]<x[j_1+1]，不等式记得变号

y[i]>\dfrac{dp[j_1]-dp[j_2]}{x[j_2+1]-x[j_1+1]}

令 t[i]=x[i+1]

则 y[i]>\dfrac{dp[j_1]-dp[j_2]}{t[j_2]-t[j_1]}

-y[i]<\dfrac{dp[j_2]-dp[j_1]}{t[j_2]-t[j_1]}

然后就是了，按照上题的分析我们可以得出我们要维护一个上凸壳

大于小于反过来就是了

注意一下我程序这里用的柿子是 y[i]>\dfrac{dp[j_1]-dp[j_2]}{t[j_2]-t[j_1]}

#include<cstring>
#include<ctime>
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<algorithm>

#define rg register
#define il inline
#define MX (50000 + 4)
#define ll long long
#define db double

struct dirt{
    int x ,y;
    bool operator <(const dirt b)const{
        return x == b.x ? y > b.y : x > b.x;
    }
}d[MX];
ll dp[MX] ,Q[MX];
double slope(int j1 ,int j2){
    return (db)(dp[j1] - dp[j2]) / (d[j2 + 1].x - d[j1 + 1].x);
}

int main(){
    int n ,cnt = 0;;
    scanf("%d" ,&n);
    for(rg int i = 1 ; i <= n ; ++i){
        scanf("%d%d" ,&d[i].x ,&d[i].y);
    }
    std::sort(d + 1 ,d + 1 + n);
    int lasty = -1;
    for(rg int i = 1 ; i <= n ; ++i){
        if(d[i].y <= lasty) continue;
        else lasty = d[i].y ,d[++cnt] = d[i];
    }
    int head = 0 ,tail = 0;
    for(rg int i = 1 ; i <= cnt ; ++i){
        while(head < tail && (d[i].y >= slope(Q[head] ,Q[head + 1])))   ++head;
        dp[i] = dp[Q[head]] + 1LL * d[Q[head] + 1].x * d[i].y;
        while(head < tail && (slope(Q[tail] ,i) <= slope(Q[tail - 1] ,Q[tail]))) --tail;
        Q[++tail] = i;
    }
    printf("%lld\n" ,dp[cnt]);
    return 0;
}

例题3 [NOI2019]回家路线

设 dp[i] 表示现在刚到第 i 条边终点花费最少时间

首先我们可以yy出一个 O(m^2) 的 dp 式子

dp[i]=\min dp[j]+A(p_i-q_j)^2+B(p_i-q_j)+C\ \ \ \ (y_j=x_i)

显然发现一个事：这式子是斜优

愉快拆拆拆，假设一个转移 j_1 比 j_2 菜，且……

等等，每一个转移又有一个 p 又有一个 q 该怎么排序呢？这怎么办呢？

惨痛的事实证明你按哪一个排都没用

我们可以把一个转移拆成【在 p_i 处询问 dp 值，然后在 q_i 处把 dp 值插入凸包】两个操作！

这样我们就可以正常排序，只需记录操作类型

还发现一件事，这不是一维序列上的 dp ，凸包到底怎么维护？

对于每一个终点都维护一个凸包用来转移就是了

即【在时间 p_i 时询问 x_i 为终点的 dp 值，然后在时间 q_i 时把 x_i 为终点的 dp 值插入 y_i 为终点的凸包里】两个操作！

我们得维护 n 个凸包，stl帮了大忙，直接开 n 个 deque 搞，空间 O(m)

于是我们毫无顾虑地愉快拆拆拆式子，假设一个转移 j_1 比 j_2 菜，且 q_{j_1}<q_{j_2}

dp[j_1]+A(p_i-q_{j_1})^2+B(p_i-q_{j_1})+C>dp[j_2]+A(p_i-q_{j_2})^2+B(p_i-q_{j_2})+C

dp[j_2]-dp[j_1]+(q_{j_1}-q_{j_2})(2Ap_i-Aq_{j_1}-Aq_{j_2}+B)<0

$$2Ap_i-Aq_{j_1}-Aq_{j_2}+B>\dfrac{dp[j_1]-dp[j_2]}{q_{j_1}-q_{j_2}}$$ $k=\dfrac{dp[j_1]-dp[j_2]}{q_{j_1}-q_{j_2}}

这就是式子 k<2Ap_i-Aq_{j_1}-Aq_{j_2}+B

下小上大倒三角，我们需要维护一个下凸包

单调性证明同例题1

贴个代码

#include<cstdio>
#include<cstring>
#include<deque>
#include<iostream>
#include<algorithm>

#define rg register
#define il inline
#define MX (200000 + 5)
#define db double
#define INF (1LL << 50)
#define ll long long

int n ,m ,A ,B ,C;
il int read()
ll min(ll a ,ll b)

struct edge{
    int x ,y ,p ,q;
    long long val;
}e[MX];
struct operation{
    int pos ,tim ,id ,belong;
    bool operator <(const operation &B)const{return tim == B.tim ? id > B.id : tim < B.tim;}
}op[MX * 2];

std::deque<int> que[MX >> 1];
ll dp[MX * 2];
db slope(int j1 ,int j2){
    if(op[j1].tim - op[j2].tim == 0)    return INF;
    return (dp[j1] - dp[j2] * 1.0) / (op[j1].tim - op[j2].tim);
}

int main(){
    n = read(); m = read();
    A = read(); B = read(); C = read();
    for(rg int i = 1 ,x ,y ,p ,q ; i <= m ; ++i){
        x = read(); y = read();
        p = read(); q = read();
        e[i] = (edge){x ,y ,p ,q ,0};
        op[i * 2 - 1] = (operation){x ,p ,1 ,i};
        op[i * 2] = (operation){y ,q ,2 ,i};
    }
    ll ans = INF;
    std::sort(op + 1 ,op + 1 + m + m);
    e[0] = (edge){0 ,1 ,0 ,0};
    op[0] = (operation){1 ,0 ,2 ,0};
    que[1].push_back(0);
    for(int i = 1 ,now ,type ; i <= m * 2 ; ++i){
        now = op[i].pos ,type = op[i].id;

        if(type == 1){
            while(que[now].size() > 1){
                int j1 = que[now].front() ,j2 = que[now].at(1);
                ll t = 1LL * A * (2 * op[i].tim - op[j1].tim - op[j2].tim) + B;
                if(slope(j1 ,j2) <= t)  que[now].pop_front();
                else break;
            }

            if(!que[now].empty()){
                int j = que[now].front();
                e[op[i].belong].val = dp[j] + 
                    1LL * A * (op[i].tim - op[j].tim) * (op[i].tim - op[j].tim) 
                    + 1LL * B * (op[i].tim - op[j].tim) + C;
            }
            else{e[op[i].belong].val = INF; continue;}
        }

        else{
            dp[i] = e[op[i].belong].val;
            while(que[now].size() > 1){
                int j1 = que[now].back() ,j2 = que[now].at(que[now].size() - 2);
                if(slope(j1 ,i) < slope(j2 ,j1))    que[now].pop_back();
                else break;
            }

            if(now == n){
                ans = min(ans ,dp[i] + op[i].tim);
                continue;
            }

            if(dp[i] < INF) que[now].push_back(i);
        }

    }
    printf("%lld\n" ,ans);
    return 0;
}

一些细节

小心算斜率的时候 \Delta x =0。

建议就记 k<a 这种形式，大于的形式可强行 *-1。

不要把 Que[tail] 写成 tail

三个决策点在同一直线时要放弃中间那个。

Part 2 二分决策点

流坑代填

P5785 [SDOI2012]任务安排

弱化版P2365 任务安排，暴力可过，没有负数。

好吧，当我们发现柿子 k < a 的右侧这个 a 没有单调性了，怎么办办呢？