【题解】P7057 [NWRRC2015]Journey to the “The World’s Start”

· · 题解

upd 2023.12.28：修改了一处代码错误。

线段树优化 dp。

题目大意

你要从第 1 个点坐地铁到第 n 个点，有 n-1 张车票，每一张车票的乘车范围为 r_i=i，并且有价格 p_i。乘车范围 r_i 表示你能从 i 点坐到 [i-r_i,i+r_i] 内的点下车（不越界），然后再上车。

在第 i 个点下车的所花时间是 d_i，第 1 和 n 个点下车不花时间，从一个点坐到另一个点需要 1 单位时间（如果 1 坐到 4，需要 3 单位时间）。你需要在 t 时间内到达 n，且只能用一种车票（可以用无数次），求车票费用最小值。

例如样例就是选择了 r_i=2 的车票，然后 1 \rightarrow 2 \rightarrow 4 即可。

题目分析

如果要从 1 坐到 n，则无论如何都要 n-1 单位时间，所以先让 t 减去 n-1。

有个很明显的单调性，就是如果 r_k 这个范围的车票可行，那么 [r_k,n-1] 范围的车票都可行。

所以只用找出来最小满足条件的 r_k，那么 [r_k,n-1] 都可行，答案便是 \displaystyle\min_{i=k}^{n-1}{p_i}。

这个东西可以用二分找，现在的关键便是如何求第 k 张车票的最短时间。

假设目前用的是第 k 张车票，范围是 r_k=k。

首先我只能坐地铁到后面的点，不然肯定不优。

然后开始想各种各样的贪心，发现都是错的（有兴趣的可以试一下能不能做）。于是开始想如何 dp。

设 f_i 为在 i 点下车的答案（最小值）。

根据前面的条件， f_i=\displaystyle\min_{j=\max(1,i-k)}^{i-1}f_j+d_i，然后 f_n 即为所求。

如果我们暴力求解，这样时间是 O(n^2) 的，带上二分变成了 O(n^2\log n)，会 T 掉。

观察式子，极其简单，只有一个区间求 \min，用线段树优化一下就行了。

时间复杂度 O(n\log ^2n)。

代码

#include<bits/stdc++.h>
#define ll long long
#define LC x<<1
#define RC x<<1|1
using namespace std;
ll n,t,p[50050],d[50050],f[50050],tree[200020],ans=8e18;
void pushup(ll x){
    tree[x]=min(tree[LC],tree[RC]);
}
void mdf(ll x,ll l,ll r,ll pos,ll v){
    if(l==r){
        tree[x]=v;
        return;
    }
    ll mid=(l+r)>>1;
    if(pos<=mid) mdf(LC,l,mid,pos,v);
    else mdf(RC,mid+1,r,pos,v);
    pushup(x);
}
ll query(ll x,ll l,ll r,ll ql,ll qr){
    if(ql<=l&&r<=qr) return tree[x];
    ll mid=(l+r)>>1,res=8e18;
    if(ql<=mid) res=min(res,query(LC,l,mid,ql,qr));
    if(mid<qr) res=min(res,query(RC,mid+1,r,ql,qr));
    return res;
}
bool chk(ll k){
    for(ll i=2;i<=n;i++){
        f[i]=query(1,1,n,max(1ll,i-k),i-1)+d[i];
        mdf(1,1,n,i,f[i]);
    }
    return f[n]<=t;
}
int main(){
    scanf("%lld %lld",&n,&t);
    t-=n-1;
    for(ll i=1;i<n;i++) scanf("%lld",&p[i]);
    for(ll i=2;i<n;i++) scanf("%lld",&d[i]);
    ll l=1,r=n-1;
    while(l<r){
        ll mid=(l+r)>>1;
        if(chk(mid)) r=mid;
        else l=mid+1;
    }
    for(ll i=l;i<n;i++) ans=min(ans,p[i]);
    printf("%lld",ans);
}