题解 AT2287 【[ARC067B] Walk and Teleport】

· · 题解

此题其实可以用斜率优化做脑子比较笨,没去想贪心
设f[i]表示到达前i个点所需要的最小花费
那么首先可以得到f[i]可以从f[i-1]得到，也就是说f[i]=min(f[i],f[i-1]+A(dis[i]-dis[i-1]))
再考虑从i-1之前的点j瞬移过来之后再往回走去遍历那些[j+1,i-1]之间的点,可以得到方程

f[i]=min(f[i],f[j]+(dis[i]-dis[j+1])*2A+B)

然后假设存在一个f[x]比f[j]转移过来更优
也就是

f[x]-f[j]-Adis[x+1]+Adis[j+1]<0\\ \frac{f[x]-f[j]}{dis[x+1]-dis[j+1]}<A

轻松得到斜率是\frac{f[x]}{dis[x+1]},且dis[x+1]与A均含有单调性A根本就是定值吧！
最后用单调队列维护一下凸包就好了
以下是代码 

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define ll long long
il ll read(){
    bool f=true;ll x=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=false;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(f) return x;
    return ~(--x);
}
il void write(const ll &x){if(x>9) write(x/10);putchar(x%10+'0');}
il void print(const ll &x) {x<0?putchar('-'),write(~(x-1)):write(x);putchar('\n');}
il int max(const int &a,const int &b){return a>b?a:b;}
il int min(const int &a,const int &b){return a<b?a:b;}
int n;
const int MAXN=1e5+7;
ll dis[MAXN];
ll f[MAXN];
ll A,B;
int q[MAXN],l,r;
#define fz(i,j) (f[i]-f[j])
#define fm(i,j) (dis[i+1]-dis[j+1])
int main(){
    n=read(),A=read(),B=read();
    for(ri i=1;i<=n;++i) dis[i]=read();
    q[r++]=1;
    for(ri i=2;i<=n;++i){
        f[i]=f[i-1]+(dis[i]-dis[i-1])*A;
        while(l+1<r&&A*fm(q[l+1],q[l])>=fz(q[l+1],q[l]))++l;
        int x=q[l];
        f[i]=min(f[i],f[x]+B+(dis[i]-dis[x+1])*A*2);
        while(l+1<r&&fz(i,q[r-1])*fm(q[r-1],q[r-2])<=fm(i,q[r-1])*fz(q[r-1],q[r-2])) --r;
        q[r++]=i;
    }
    print(f[n]);
    return 0;
}

其实回到刚才的斜率那里，已经证明贪心的正确性了
把柿子再化一下,就相当于只要从从j到x走过去的花费大于B,那么直接瞬移一定更优