[APC001] Ex - Separation

ivyjiao · 2024-09-08 16:17:41 · 题解

先考虑什么时候无解：当 c<2\times x 时，ivyjiao 出不了门，取不了货物。有特例为 \sum_{i=1}^{i\leq n}b_i=0 时，根本没有货物，此时要输出 0。

再考虑怎样能够让一份货物的亏损最少。由于一份货物的所处位置分为“在仓库中”和“在 ivyjiao 的背包中”，而第二段的时间是一定的，就是 x-a_i，i 为这份货物在哪个工厂生产出来，所以第二段的亏损也是一定的，就是 m\times(x-a_i)。综上所述，可知这一段总的亏损也是一定的，就是：

而第一段的时间是可控的，最小是 0，也就是这份货物刚被生产出来，就被 ivyjiao 取走了。接下来我们只考虑第一段的亏损。

由于有分身制造器，我们可以随意往返。接下来我们还能发现总共往返的次数也是一定的，因为初始体力不变，是 c，中途没有恢复体力的手段，往返一次消耗的体力也是一定的，是 2\times x，又因为需要保证在任何时候，现有体力都能支持每一个分身（包括本体）返回 A 地，所以总共能往返 \lfloor\dfrac{c}{2\times x}\rfloor 次。

由上述两个性质，我们可以看出每次往返必能正好取走至少一份货物，因为如果一份货物都不能正好取走，我们定能通过改变出发时间来让这次往返正好取走至少一份货物，而这样肯定是更优的。

为了方便计算，我们对于每份货物，计算出它在什么时间出发能被正好取走，并将其从小到大排序，这样在取走一份货物时，就能取走所有比它编号要小的货物，更容易计算。设对于排完序后的货物，在 s_i 时间出发能够将其正好取走，sum_i=\sum_{j=1}^{j\leq i} s_j，如果上一次正好取走了第 i 份货物，这一次正好取走了第 j 份货物，那么从 i+1 到 j 这一段的货物的受潮时间就为：

拆括号得到：

亏损的钱数就为：

这时候有人可能会发现：s_i 可能 <k。这时候就用到时光穿梭机了，容易发现这次时光穿梭机什么时候用都一样，不影响答案，只需要穿越到 \min\{s_i\} 以前就行。

感觉很可以 dp。设 dp_{i,j} 为只考虑在 [1,j] 份货物中，往返第 i 次正好取走排序后第 j 份货物亏损的最小值，答案即为 dp_{\lfloor\frac{c}{2\times x}\rfloor,\sum_{i=1}^{i\leq n} b_i}。

再来推一下 dp 式。根据上文亏损钱数可知：

欸？\min_{k=1}^{k\leq j}？s_j\times k？这咋这么像斜率优化 dp 啊？

接着推下去：

把 \min 去掉，得：

化成斜率优化 dp 的 y=kx+b 形式，得：

标明一下：

至此已化成 y=kx+b 的形式。

注意因为我们求的是最小值，所以最开始的 dp 数组要赋成极大值并把 dp_{i,0} 清零，或者预处理出 dp_1 里的每个值。

最后统计答案，答案即为：

最后就是输出方案了，在 dp 的过程中记录一下每个值是由哪个地方转移而来，设 dp_{i,j} 是由 dp_{i-1,fa} 转移而来，那么我们就让 fa_{i,j}=x，输出时不断跳 fa 数组，并用 set 记录，判断每次出发时是否有分身（或者本体）在家即可，别忘了 -k。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,x,c,k,a[200001],b[200001],sumb,d,s[500001],l,sum[500001],fa[201][500001],dp[201][500001],q[200001],f[201],r,now,ans;
set<int>st;
int X(int j){
    return j;
}
int Y(int j){
    return dp[now][j]+m*sum[j];
}
double query(int i,int j){
    return 1.0*(Y(j)-Y(i))/(X(j)-X(i));
}
void print(int k,int x){
    if(k-1&&fa[k][x]) print(k-1,fa[k][x]);
    f[++r]=x;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        sumb=0,l=0,r=0,ans=0;
        st.clear();
        cin>>n>>m>>x>>c>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            cin>>b[i];
            sumb+=b[i];
            ans+=b[i]*m*(x-a[i]);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=b[i];j++){
                cin>>d;
                s[++l]=d-a[i];
            }
        }
        if(!sumb){
            cout<<0<<'\n';
            cout<<-1<<" "<<-1<<'\n';
            continue;
        }
        if(!(c/(2*x))){
            cout<<-1<<'\n';
            continue;
        }
        sort(s+1,s+1+l);
        for(int i=1;i<=l;i++){
            sum[i]=sum[i-1]+s[i];
            dp[1][i]=m*(s[i]*i-sum[i]);
        }
        int h=1,t=1;
        for(int i=2;i<=c/(2*x);i++){
            h=1,t=1,now=i-1;
            memset(q,0,sizeof q);
            for(int j=1;j<=l;j++){
                while(h<t&&query(q[h],q[h+1])<=m*s[j]) h++;
                dp[i][j]=dp[i-1][q[h]]+m*((j-q[h])*s[j]-sum[j]+sum[q[h]]);
                fa[i][j]=q[h];
                while(h<t&&query(q[t-1],j)<=query(q[t-1],q[t])) t--;
                q[++t]=j;
            }
        }
        cout<<dp[c/(2*x)][l]+ans<<'\n';
        print(c/(2*x),l);
        for(int i=1;i<=r;i++){
            if(i==1){
                cout<<s[f[i]]-k<<" "<<0<<'\n';
                st.insert(s[f[i]]+2*x);
                continue;
            }
            if(!st.size()){
                cout<<s[f[i]]-k<<" "<<1<<'\n';
                st.insert(s[f[i]]+2*x);
                continue;
            }
            bool sepa=1;
            if(*st.begin()<=s[f[i]]){
                st.erase(st.begin());
                sepa=0;
            }
            cout<<s[f[i]]-k<<" "<<sepa<<'\n';
            st.insert(s[f[i]]+2*x);
        }
        cout<<-1<<" "<<-1<<'\n';
    }
}