题解：P14460 【MX-S10-T1】『FeOI-4』寻雾启示

· · 题解

简单题。

设 f(i) 表示 i 的答案。

则有转移：

f(i) = \min_{j < i} f(j) + t_2 \cdot j + \max(0,i \cdot k - (f(j) + t_2 \cdot j)) + t_2 \cdot j + t_1 \cdot (i - j)

发现带 j 的都是简单的，线段树一下就行，唯一就是 \max 那个式子，由于 f 是单增的，所以可以二分找到最后一个满足 i \cdot k - (f(j) + t_2 \cdot j) \ge 0 的位置，然后分别维护两颗线段树，一颗不用关系 \max 的式子，另一颗对于点 i 有额外的 f(i) + t_2 \cdot i 的贡献，时间复杂度 \mathcal O(Tn\log n)。 :::success[代码]

#include <bits/stdc++.h>

constexpr int N = 1e5 + 5;

long long f[N],m,k,t1,t2;

inline void chkmin(long long & x,long long y){
    x = (y < x ? y : x);
}
struct segment_tree{
    long long mn[N << 2];
    inline int ls(int x){
        return x << 1;
    } 
    inline int rs(int x){
        return x << 1 | 1;
    }
    inline void push_up(int x){
        mn[x] = std::min(mn[ls(x)],mn[rs(x)]);
    }
    inline void build(int u,int l,int r){
        mn[u] = 1e18;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(ls(u),l,mid);
        build(rs(u),mid + 1,r);
    }
    inline void update(int u,int l,int r,int x,long long val){
        if(l == r){
            mn[u] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) update(ls(u),l,mid,x,val);
        else update(rs(u),mid + 1,r,x,val);
        push_up(u);
    }
    inline long long query(int x,int l,int r,int ql,int qr){
        if(ql <= l && qr >= r){
            return mn[x];
        }
        long long Min = 1e18,mid = (l + r) >> 1;
        if(ql <= mid) chkmin(Min,query(ls(x),l,mid,ql,qr));
        if(qr > mid) chkmin(Min,query(rs(x),mid + 1,r,ql,qr));
        return Min;
    }
}T1,T2;
inline void solve(){
    std::cin >> m >> k >> t1 >> t2;
    f[0] = 0;
    T1.build(1,1,m);
    T2.build(1,1,m);
//  for(int i = 1; i <= m; ++ i){
//      f[i] = 1e18;
//      long long t = 1ll * i * k;
//      for(int j = 0; j < i; ++ j){
//          long long reach = f[j] + 1ll * t2 * j;
//          chkmin(f[i],reach + std::max(0ll,t - reach) + t2 * j + t1 * (i - j));
//      }
//  }
    for(int i = 1; i <= m; ++ i){
        f[i] = 1e18;
        long long t = 1ll * i * k;

        for(int j = 0; j <= 0; ++ j){
            long long reach = f[j] + 1ll * t2 * j;
            chkmin(f[i],reach + std::max(0ll,t - reach) + t2 * j + t1 * (i - j));
        }
        int l = 1,r = i - 1,ans = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            long long reach = f[mid] + mid * t2;
            if(reach <= t){
                l = mid + 1;
                ans = mid;
            }else{
                r = mid - 1;
            }
        }
        if(ans > 0){
            chkmin(f[i],t + t1 * i + T1.query(1,1,m,1,ans));
        }
        if(ans + 1 < i){
            chkmin(f[i],t1 * i + T2.query(1,1,m,ans + 1,i - 1));
        }
        long long reach = f[i] + 1ll * t2 * i;
        T1.update(1,1,m,i,t2 * i - t1 * i);
        T2.update(1,1,m,i,reach + t2 * i - t1 * i);
    }
    for(int i = 1; i <= m; ++ i){
        std::cout << f[i] << ' ';
    }
    std::cout << '\n';
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while(T -- ){
        solve();
    }
    return 0;
}

:::