IOI2009 旅行商

题目:

   旅行商认定如何优化旅行路线是一个非常棘手的计算问题,所以他决定沿着线性的多瑙河开展他的业务。他有一条快船能够在瞬间沿着多瑙河把他从任意开始的位置带到任意目的地,但是这条船很费油。它逆流而上(驶向源头的方向)每米花费U元,顺流而下每米花费D元(驶离源头的方向)。
   沿着多瑙河有N个展销会是旅行商所感兴趣的。每个展销会只持续一天。对于任意一个展销会X,旅行商知道:
   ①展销日期是Tx(该日期是从旅行商买船之日算起过去的天数)
   ②展销地点是Lx(该地点用它与源头的距离表示,单位为米)
   ③参加该展销会能赚到的钱数是Mx元。
   旅行商开始和结束旅程的地点都是他位于多瑙河边的家S (用它与源头的距离表示,单位为米)。
   请帮助旅行商选择他是否参加,如果参加应该以什么样的顺序参加哪些展销会才能在旅行结束时获得最多的总收益。旅行商的总收益定义为他参加的所有展销会的收益和,减去他在河上顺流和逆流航行的总花费。
   注意:如果展销会A在展销会B之前举行并且旅行商要参加这两个展销会,旅行商必须先参加A,之后才能参加B(即他不能先参加B后参加A)。当两个展销会在同一天举行,他可以按任意顺序参加这两个展销会。旅行商在一天之内参加的展销会的数目没有限制,但是他不能参加同一个展销会两次并在一个展销会上获得两次收益。他可以经过他已经参加过的展销会而不再获得任何收益。
   任务:
   写一个程序,给定所有展销会的日期、地点和收益,以及旅行商的家的位置和他旅行的花费,计算他在旅行结束时可能获得的最大的总收益。

思路:

   先考虑没有展览会在同一天的情况。不难得到:
  
  
   如果把这些值根据排好,那么转移可以分离变量后用树状数组求一个前缀、后缀最大值即可。
   再考虑多个展览会在同一天的情况。显然如果用多个展览会可以去,那么去的肯定是连续的一段。设表示参加从左往右或从右往左决策到第个展览会的最大收益,初值就等于。参加多个展览会的转移就是:
  
  
   这个直接扫一遍即可。

代码:

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
#define mset(a,b) memset(a,b,sizeof a)
#define File(_) freopen(#_".in","r",stdin),freopen(#_".out","w",stdout)
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
const int MN=5e5+5;
struct Data{
    int t,l,m;
    bool operator < (const Data &d) const {
        return t==d.t?l<d.l:t<d.t;
    }
}a[MN];
typedef long long ll;
struct BIT{
    #define low(x) (-(x)&(x))
    ll c1[MN],c2[MN],a;
    BIT(){mset(c1,0x8f);mset(c2,0x8f);}
    void updL(int x,ll v){
        for(;x<MN;x+=low(x))
            tomax(c1[x],v);
    }
    void updR(int x,ll v){
        for(;x;x-=low(x))
            tomax(c2[x],v);
    }
    ll qryL(int x){
        for(a=-1e9;x;x-=low(x))
            tomax(a,c1[x]);
        return a;
    }
    ll qryR(int x){
        for(a=-1e9;x<MN;x+=low(x))
            tomax(a,c2[x]);
        return a;
    }
}c;
ll dp[MN],tmp[MN][2];
int main(){
//  File(salesman);
    int n,u,d,s;
    scanf("%d%d%d%d",&n,&u,&d,&s);
    rep(i,1,n)
        scanf("%d%d%d",&a[i].t,&a[i].l,&a[i].m);
    std::sort(a+1,a+1+n);
    c.updL(s,s*d);
    c.updR(s,-s*u);
    rep(r,1,n){
        int l=r;
        for(;a[l].t==a[r].t;r++);
        r--;
        rep(i,l,r){
            ll val=std::max(c.qryL(a[i].l)+a[i].m-a[i].l*d,c.qryR(a[i].l)+a[i].m+a[i].l*u);
            tmp[i][1]=tmp[i][0]=val;
        }
        rep(i,l+1,r)
            tomax(tmp[i][0],tmp[i-1][0]-(a[i].l-a[i-1].l)*d+a[i].m);
        drep(i,r-1,l)
            tomax(tmp[i][1],tmp[i+1][1]-(a[i+1].l-a[i].l)*u+a[i].m);
        rep(i,l,r){
            dp[i]=std::max(tmp[i][0],tmp[i][1]);
            c.updL(a[i].l,dp[i]+a[i].l*d);
            c.updR(a[i].l,dp[i]-a[i].l*u);
        }
    }
    ll ans=0;
    rep(i,1,n){
        if(a[i].l>s)
            tomax(ans,dp[i]-(a[i].l-s)*u);
        else
            tomax(ans,dp[i]-(s-a[i].l)*d);
    }
    printf("%lld\n",ans);
    /*
    dp[i]=dp[j]-l[i]*d+l[j]*d+m[i]
    dp[i]=dp[j]-l[j]*u+l[i]*u+m[i]
    */
    return 0;
}