第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到10^8之间）和馅饼的个数n（1到10^5）。 接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的t[i]和p[i]都一样。
一个数，表示游戏者获得的最大总得分。
一道经典的二维偏序问题。至于怎么将原题目转换为二维偏序？？
首先可以将每秒走一步和两步转换为在一秒钟走一步或半步，即把时间加倍。接下来考虑dp转移。能从j转移到i当且仅当ti-tj>=|pi-pj|，可以转换为两个式子：pi>=pj时，ti-pi>=tj-pj，又因为pi-pj此时是正数，所以pj-pi是负数，因为ti-tj此时已经大于一个正数，则它也一定大于负数，即ti-tj>=pj-pi也成立，即ti+pi>=tj+pj一定成立，同理pi<pj时，ti+pi>=tj+pj，ti-pi>=tj-pj也一定成立。所以满足条件的转移一定满足这两个式子。而满足这两个式子时，ti-tj一定是个正数。所以不用考虑ti的顺序了。
设val1=ti+pi,val2=ti-pi，则转换为了一个二维偏序问题。一维排序，一维用值域树状数组或者值域线段树优化。【注意】因为t值非常大，需要离散化值域。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #define ll long long 5 using namespace std; 6 7 int w, n; 8 ll val2[100005], pos[100005]; 9 10 struct node { 11 ll val1, val2; 12 int t, p, v; 13 } pie[100005]; 14 15 ll TR[400005]; 16 17 bool cmp ( node a, node b ) { 18 return a.val1 < b.val1; 19 } 20 21 void update ( int nd ) { 22 TR[nd] = max ( TR[nd << 1], TR[nd << 1 | 1] ); 23 } 24 25 void insert ( int nd, int l, int r, int pos, ll delta ) { 26 if ( l == r ) { 27 TR[nd] = delta; 28 return ; 29 } 30 int mid = ( l + r ) >> 1; 31 if ( pos <= mid ) insert ( nd << 1, l, mid, pos, delta ); 32 else insert ( nd << 1 | 1, mid + 1, r, pos, delta ); 33 update ( nd ); 34 } 35 36 ll query ( int nd, int l, int r, int L, int R ) { 37 if ( l >= L && r <= R ) return TR[nd]; 38 int mid = ( l + r ) >> 1; 39 ll ans = 0; 40 if ( L <= mid ) ans = max ( ans, query ( nd << 1, l, mid, L, R ) ); 41 if ( R > mid ) ans = max ( ans, query ( nd << 1 | 1, mid + 1, r, L, R ) ); 42 return ans; 43 } 44 45 int main ( ) { 46 scanf ( "%d%d", &w, &n ); 47 for ( int i = 1; i <= n; i ++ ) { 48 scanf ( "%d%d%d", &pie[i].t, &pie[i].p, &pie[i].v ); 49 pie[i].val1 = pie[i].t * 2 + pie[i].p; 50 pie[i].val2 = pie[i].t * 2 - pie[i].p; 51 val2[i] = pie[i].val2; 52 } 53 sort ( pie + 1, pie + 1 + n, cmp ); 54 sort ( val2 + 1, val2 + 1 + n ); 55 int w = unique ( val2 + 1, val2 + 1 + n ) - val2 - 1; 56 for ( int i = 1; i <= n; i ++ ) { 57 int pr = lower_bound ( val2 + 1, val2 + 1 + w, pie[i].val2 ) - val2; 58 ll tmp = query ( 1, 1, w, 1, pr ); 59 ll dp = tmp + pie[i].v; 60 insert ( 1, 1, w, pr, dp ); 61 } 62 printf ( "%lld", TR[1] ); 63 return 0; 64 }
原文：https://www.cnblogs.com/wans-caesar-02111007/p/9488610.html