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

· · 题解

赛时做法。

首先考虑怎么做到 O(m^2) 的复杂度。

考虑 dp，设 dp_i 表示已经放置了 i 个羊毛且现在在位置 0 所需的最小时间。

转移只需要考虑搭最后一次羊毛之前已经搭了多少羊毛。

dp_i=\min_{j=0}^{i-1} \{\max(dp_j,i\times k)+t_2\times j+t_1\times(i-j)+t_2\times i\}

解释一下实际意义。

首先你需要保证在出发之前一共能换出来 i 块羊毛，所以时间要和 i\times k 取较大值，表示如果羊毛不够的话就等到羊毛足够。然后走到现有的羊毛的尽头，搭羊毛，返回位置 0。

到位置 i 的答案就是 dp_i-i\times t_2，表示你不用再走回到 0 位置了。

考虑优化，先把式子化开。

dp_i=\min_{j=0}^{i-1} \{\max(dp_j,i\times k)+(t_2-t_1)\times j\}+(t_1+t_2)\times i

通过观察这个式子我们可以如果 t_2-t_1\ge 0，则随着 j 增大，内层的贡献单调不降，所以令 j 取 0 最优。

接下来考虑 t_2-t_1<0 的情况。

发现内层的 max 十分的恶心，所以我们通过分讨拆掉这个 max。显然 dp 数组单调递增，所以取到 i\times k 的 j 是一个前缀。我们设 p 表示最大的 j 满足 dp_j<i\times k，显然 p 及以前的位置只与 j 有关，且 j 越大答案越小，所以 p 前的所有决策点都不优。至于 p 以后的决策点，用一个 multiset 维护所有的决策即可快速得到答案。

// Problem: P14460 【MX-S10-T1】『FeOI-4』寻雾启示
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14460
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define retunr return
bool startmb;
constexpr int N=1e5+5;
int _,n,k,x,y;

int dp[N];

multiset<int> s;

bool endmb;
main()
{
    cerr<<((&startmb-&endmb)/1024.0/1024)<<endl;
    cin.tie(0)->sync_with_stdio(false);
    cin>>_;
    while(_--)
    {
        cin>>n>>k>>x>>y;
        if(y-x>=0)
        {
            for(int i=1;i<=n;i++) cout<<i*k+x*i<<' ';
            cout<<'\n';
        }
        else
        {
            s.insert(0);
            for(int i=1,p=0;i<=n;i++)
            {
                while(p<i&&dp[p]<=i*k) s.extract(dp[p]+(y-x)*p),p++;//维护p的位置
                dp[i]=i*k+(y-x)*(p-1);
                if(s.size()) dp[i]=min(dp[i],*s.begin());//p后的答案
                dp[i]+=(x-y)*i+y*i*2;
                s.insert(dp[i]+(y-x)*i);
            }
            for(int i=1;i<=n;i++) cout<<dp[i]-y*i<<' ';
            cout<<endl;
        }
        s.clear();
    }
    return 0;
}