這題有個關鍵(?) ： 所有的位置 (展覽 + 家) 都不一樣。
所以，先考慮 60 pts (沒有兩個展覽在同一天)，這個可以用DP去實現。
dp[i] --> 在位置 i 當作最後一個 展覽，最佳的獲利是多少。
這樣一來， dp[i] = max( dp[j] + cost(i,j) ) ， 其中 cost (i,j) 是 位置 i 到位置 j 的距離。
因為距離的cost有兩種：一種是 用 U 的，一種是用 D 的，所以要開兩個線段樹分別存下來(?
這樣，就可以在 O(N lg N) 的複雜度解決這題。
接下來，考慮 有多個展覽在同一天。
可以發現，對於最佳解，有一個固定的pattern是：先走到某一個展覽，在一直延那個展覽往右 / 往左走。
於是，好好地用上面那個線段樹搞一搞，就okay惹~
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define F first #define S second #define SZ(x) ((int)(x).size()) pii operator+(const pii &p1,const pii &p2) { return make_pair(max(p1.F,p2.F),max(p1.S,p2.S)); } const int INF = 2000000009; const int POS_MAX = 500004; const int POS_MIN = -1; pii ee = make_pair(-INF,-INF); struct Node { Node *lc,*rc; pii val; Node():lc(NULL),rc(NULL),val(ee){} void pull() { val = (lc->val + rc->val); } }; Node* Build(int L,int R) { Node* node = new Node(); if (L==R) { return node; } int mid=(L+R)>>1; node->lc = Build(L,mid); node->rc = Build(mid+1,R); return node; } void modify(Node* node,int L,int R,int pos,pii val) { if (L == R) { node->val = val; return; } int mid=(L+R)>>1; if (pos <= mid) modify(node->lc,L,mid,pos,val); else modify(node->rc,mid+1,R,pos,val); node->pull(); } pii query(Node* node,int L,int R,int l,int r) { if (l>R || L>r) return ee; else if (l<=L && R<=r) return node->val; int mid=(L+R)>>1; return (query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r)); } int dp[POS_MAX]; int t[POS_MAX],l[POS_MAX],m[POS_MAX]; vector<int> tt[POS_MAX]; int main () { int n,u,d,s; scanf("%d %d %d %d",&n,&u,&d,&s); ++s; int nn = 500003; Node* root = Build(1,nn); for (int i=1;n>=i;i++) { scanf("%d %d %d",&t[i],&l[i],&m[i]); ++l[i]; tt[ t[i] ].push_back(i); } //swap(d,u); modify(root,1,nn,s, make_pair( dp[s]-(s-POS_MIN)*u , dp[s]-(POS_MAX-s)*d ) ); for (int ii=1;nn>=ii;ii++) { //if (SZ(tt[ii]) != 1) continue; //cout << "ii = " << ii << endl; if (SZ(tt[ii]) >= 1) { for (int i:tt[ii]) { pii p = query(root,1,nn,1,l[i]-1); pii q = query(root,1,nn,l[i]+1,nn); int mx = -INF; if (p.S != -INF) { mx = max(mx,p.S + (POS_MAX-l[i])*d); } if (q.F != -INF) { mx = max(mx,q.F + (l[i]-POS_MIN)*u); } dp[ l[i] ] = mx + m[i]; //cout << "dp [ " << l[i] << " ] = " << dp[ l[i] ] << endl; //modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) ); } for (int i:tt[ii]) { modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) ); } } if (SZ(tt[ii]) > 1) { sort(tt[ii].begin(),tt[ii].end(),[](const int &a,const int &b) { return l[a] < l[b]; }); //starting from l --> r pii ptmp = query(root,1,nn,1,l[ tt[ii][0] ]-1); int lmax = ptmp.S; for (int iii=0;SZ(tt[ii])>iii;iii++) { int i = tt[ii][iii]; dp[ l[i] ] = max( dp[ l[i] ], lmax + (POS_MAX - l[i])*d + m[i] ); lmax += m[i]; if (iii == SZ(tt[ii]) - 1) break; int nxti = tt[ii][iii+1]; pii qtmp = query(root,1,nn,l[i],l[nxti]-1); lmax = max(lmax,qtmp.S); } //starting from r --> l reverse(tt[ii].begin(),tt[ii].end()); ptmp = query(root,1,nn,l[ tt[ii][0] ]+1,nn); int rmax = ptmp.F; for (int iii=0;SZ(tt[ii])>iii;iii++) { int i = tt[ii][iii]; dp[ l[i] ] = max( dp[ l[i] ], rmax + (l[i] - POS_MIN)*u + m[i]); rmax += m[i]; if (iii == SZ(tt[ii]) - 1) break; int nxti = tt[ii][iii+1]; pii qtmp = query(root,1,nn,l[nxti]+1,l[i]); rmax = max(rmax,qtmp.F); } /*reverse(tt[ii].begin(),tt[ii].end()); for (int iii=1;SZ(tt[ii])>iii;iii++) { int i = tt[ii][iii]; int prei = tt[ii][iii-1]; dp[i] = max(dp[i],dp[prei] + (l[i] - l[prei])*d); } reverse(tt[ii].begin(),tt[ii].end()); for (int iii=1;SZ(tt[ii])>iii;iii++) { int i = tt[ii][iii]; int prei = tt[ii][iii-1]; dp[i] = max(dp[i],dp[prei] + (l[prei] - l[i])*u); }*/ for (int i:tt[ii]) { modify(root,1,nn,l[i], make_pair( dp[ l[i] ]-( l[i] -POS_MIN)*u , dp[ l[i] ]-(POS_MAX- l[i] )*d ) ); } } } //swap(d,u); int ans = 0; for (int i=1;POS_MAX>i;i++) { /*if (dp[i]) { cout << "i = " << i << " , dp = " <<dp[i] << endl; }*/ if (i < s) { ans = max(ans,dp[i] - (s-i)*d); } else { ans = max(ans,dp[i] - (i-s)*u); } } printf("%d\n",ans); }
