题干：
YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city A to southeastern city B. Let us assume that A is(0,0)(0,0)on the rectangle map and B(109,109)(109,109). YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at(x,y)(x,y)now(0≤x≤109,0≤y≤109)(0≤x≤109,0≤y≤109), he will only forward to(x+1,y)(x+1,y),(x,y+1)(x,y+1)or(x+1,y+1)(x+1,y+1).
On the rectangle map from(0,0)(0,0)to(109,109)(109,109), there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a villagekkon(xk,yk)(xk,yk)(1≤xk≤109,1≤yk≤109)(1≤xk≤109,1≤yk≤109), only the one who was from(xk−1,yk−1)(xk−1,yk−1)to(xk,yk)(xk,yk)will be able to earnvkvkdollars.(YJJ may get different number of dollars from different village.)
YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.
Input
The first line of the input contains an integerTT(1≤T≤10)(1≤T≤10),which is the number of test cases.
In each case, the first line of the input contains an integerNN(1≤N≤105)(1≤N≤105).The followingNNlines, thekk-th line contains 3 integers,xk,yk,vkxk,yk,vk(0≤vk≤103)(0≤vk≤103), which indicate that there is a village on(xk,yk)(xk,yk)and he can getvkvkdollars in that village.
The positions of each village is distinct.
Output
The maximum of dollars YJJ can get.
Sample Input
131 1 11 2 23 3 1
Sample Output
3
题目大意：
商人从（0,0）走到（1e9，1e9）途中有若干村庄，商人可以向（x，y+1）（x+1, y）（x+1, y+1）三个方向前进，当向（x+1,y+1）方向前进时可以获得村庄（x+1, y+1）的利润，问商人途中最多可以挣多少钱
解题报告：
商人到达点（x,y）的最大利润一定是从（0,0）到（x-1，y-1）这个矩形转移而来的，但是如果单纯的用二维来dp会超空间，可以考虑dp的顺序而降低dp维度，dp顺序从上到下，从右到左，这样dp[i] = max(dp[k]) + val[i][j] 1 < K < i这样就降低了一维，用树状数组来处理前缀最大值。
AC代码：
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<map>#include<vector>#include<set>#include<string>#include<cmath>#include<cstring>#define F first#define S second#define ll long long#define pb push_back#define pm make_pairusing namespace std;typedef pair<int,int> PII;const int MAX = 2e5 + 5;struct Point {int x,y,v;bool operator <(const Point & b) const {if(x != b.x) return x < b.x;else return y > b.y;}} p[MAX];int b[MAX],c[MAX],ans,n;int get(int x) {return lower_bound(b+1,b+n+1,x) - b;}int query(int x) {int res = 0;while(x > 0) {res = max(res,c[x]);x -= x&-x;}return res;}void update(int x,int val) {while(x < MAX) {c[x] = max(c[x],val);x += x&-x;}}int main(){int t;cin>>t;while(t--) {cin>>n;ans=0;for(int i = 1; i<=n; i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v),b[i] = p[i].y,c[i] = 0;sort(b+1,b+n+1);sort(p+1,p+n+1);for(int i = 1; i<=n; i++) {int pos = get(p[i].y);int val = query(pos-1) + p[i].v;ans = max(ans,val);update(pos,val);}printf("%d\n",ans);}return 0 ;}
