题解：P5902 [IOI 2009] Salesman

· · 题解

今天模拟赛场切了，纪念一下

思路

首先看到这个题是不是很像分层跑 dp。

然后恭喜你知道这题怎么写了，完结撒花。

想到按照时间分层跑 dp 之后，我们考虑如何维护掉头之后重新碰到没有贡献，我们考虑每过一天只有一直朝着当前第一次面向的位置走才有贡献，掉头后不计贡献，这为什么是对的呢？

你可能会想到 x < i < y，我需要先从 i 到 x 再从 x 到 y，这种情况的话，你会发现不考虑花费，则贡献与直接 x 到 y 相同。通过这个例子我们发现，先往一边走，然后掉头再走是无用的，我们只需要在一天快要结束时将船开到指定的地点，然后再在新的一天开始时在赚钱，这样就达成了我们的目的。

简单理解就是早上开船去展销会赚钱，晚上找个好的地方过夜，然后方便明天早上赚钱。

这样的话我们就只要考虑优化了，首先从之前的位置转到当前位，只需要简单线段树求一下就行了。然后考虑往指定方向走，可以考虑求前缀给出的最大贡献是什么，然后简单转一下就可以了。

::::success[代码]

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define endl '\n'
using namespace std;
constexpr int N=5e5+5;
int n,u,d,S,dp[N],d_L[N],c_L[N],mn_L[N],d_R[N],c_R[N],mn_R[N],f[N];
struct node_{int l,m;};
bool cmp(node_ tim_A,node_ tim_B){
    return tim_A.l<tim_B.l;
}
vector<node_>tim[N];
struct node{int l,r,ans,tag;};
struct segtree{
    node tree[N*4];
    void update(int p,int val){
        tree[p].ans+=val;
        tree[p].tag+=val;
    }
    void down(int p){
        if(!tree[p].tag)return;
        update(p*2,tree[p].tag);
        update(p*2+1,tree[p].tag);
        tree[p].tag=0;
    }
    void up(int p){
        tree[p].ans=max(tree[p*2].ans,tree[p*2+1].ans);
    }
    void build(int p,int l,int r){
        tree[p].l=l;tree[p].r=r;
        tree[p].tag=0;
        if(l==r){
            tree[p].ans=dp[l];
            return;
        }
        int mid=(l+r)/2;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        up(p);
    }
    void modify(int p,int l,int r,int val){
        if(l<=tree[p].l&&tree[p].r<=r){
            update(p,val);
            return;
        }
        down(p);
        if(l<=tree[p*2].r)modify(p*2,l,r,val);
        if(tree[p*2+1].l<=r)modify(p*2+1,l,r,val);
        up(p);
    }
    int query(int p,int l,int r){
        if(l<=tree[p].l&&tree[p].r<=r)return tree[p].ans;
        down(p);
        int ans=-1e9;
        if(l<=tree[p*2].r)ans=max(ans,query(p*2,l,r));
        if(tree[p*2+1].l<=r)ans=max(ans,query(p*2+1,l,r));
        return ans;
    }
}seg_1,seg_2; 
void solve(){
    cin>>n>>u>>d>>S;
    tim[0].push_back({S,0});
    int maxn=0;
    for(int i=1;i<=n;i++){
        int T,L,M;
        cin>>T>>L>>M;
        tim[T].push_back({L,M});
        maxn=max(maxn,T);
    }
    tim[maxn+1].push_back({S,0});
    for(int i=1;i<=N-4;i++)dp[i]=-1e9;
    dp[S]=0;
    seg_1.build(1,1,N-4);
    seg_2.build(1,1,N-4);
    for(int i=1;i<=N-4;i++){
        seg_1.modify(1,i,i,i*d);
        seg_2.modify(1,i,i,-i*u);
    }
    for(int i=0;i<=maxn+1;i++)sort(tim[i].begin(),tim[i].end(),cmp);
    for(int i=1;i<=maxn+1;i++){
        for(int j=0;j<(int)tim[i].size();j++){
            int l=tim[i][j].l,m=tim[i][j].m;
            f[l]=dp[l];
            dp[l]=max(seg_1.query(1,1,l)-l*d,seg_2.query(1,l,N-4)+l*u);
        }
        for(int j=0;j<(int)tim[i].size();j++){
            int l=tim[i][j].l,m=tim[i][j].m;
            if(j==0)c_L[j]=m;
            else c_L[j]=c_L[j-1]+m;
            d_L[j]=-(l*d)+c_L[j];
            if(j==0)mn_L[j]=-(l*d)-dp[l];
            else mn_L[j]=min(mn_L[j-1],-(l*d)+c_L[j-1]-dp[l]);
        }
        for(int j=(int)tim[i].size()-1;j>=0;j--){
            int l=tim[i][j].l,m=tim[i][j].m;
            if(j==(int)tim[i].size()-1)c_R[j]=m;
            else c_R[j]=c_R[j+1]+m;
            d_R[j]=(l*u)+c_R[j];
            if(j==(int)tim[i].size()-1)mn_R[j]=(l*u)-dp[l];
            else mn_R[j]=min(mn_R[j+1],(l*u)+c_R[j+1]-dp[l]);
        }
        for(int j=0;j<(int)tim[i].size();j++){
            int l=tim[i][j].l,m=tim[i][j].m;
            seg_1.modify(1,l,l,-f[l]);
            seg_2.modify(1,l,l,-f[l]);
            dp[l]=max(d_L[j]-mn_L[j],d_R[j]-mn_R[j]);
            seg_1.modify(1,l,l,dp[l]);
            seg_2.modify(1,l,l,dp[l]);
        }
    }
    cout<<dp[S]<<endl;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T=1;
//  cin>>T;
    while(T--)solve();
    return 0;
}

::::