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

· · 题解

NOIP 模拟赛怎么出上绿了，这么蒸蒸日上吗 /jk

观察题目形式，要对 [1,m] 分别求解，那大概率可以递推吧。

刻画这个东西的性质，容易发现应当是在刷出充足的钱以前会预处理一段羊毛，然后在钱够了的时候抵达出生点拿钱，然后从出生点出发，一段跑步一段搭路。

显然在固定的时间内预处理的越长越好，于是考虑二分。

那接下来就是如何确定某一个长度修建的最短时间了。

贪心啥的被爆炸了，一筹莫展。

然后你突然注意到这个东西前面求过，也就是某一个 d 的答案。

那直接搞递推状物对答案上个记忆化就做完了。

然后我们其实还允许在钱全刷出来以后多拓展一格的预搭路，因为时间不是对齐的，可能多搭一个会超时但是直接返程要在出生点等很久，这样就不优。

但是拓展两格就会浪费，计算贡献容易证明一定不优于拓展一格。

注意不要忘记预搭路完还需要返程，这个贡献千万别忘算了。

要开 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int asn[100005];
void solve(){
    int n,k,t1,t2;
    cin>>n>>k>>t1>>t2;
    if(t1<=t2){
        for(int i=1;i<=n;i++)
        cout<<i*t1+i*k<<' ';
        return;
    }
    for(int i=1;i<=n;i++){
        int l=0,r=i-1;
        while(l<r){
            int mid=(l+r+1)>>1;
            int check=asn[mid]+mid*t2;
            if(check<=i*k)l=mid;
            else r=mid-1;
        }
        int ans=i*k+l*t2+(i-l)*t1;
        if(l<i-1)l++,ans=min(ans,l*t2+(i-l)*t1+max(i*k,asn[l]+l*t2));
        cout<<ans<<' ';
        asn[i]=ans;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    int t;
    cin>>t;
    while(t--)solve(),cout<<'\n';
    return 0;
}
//「对了，我的帕西瓦尔呢？」
//「哎呀，哈哈哈～」

// 她边笑边把手里的东西给他看。
// 那是一个白色的剑柄。
// 不对，那原本是一把剑，只是剩下剑柄而已。

//「对不起，融化了。」