HDU 6447 YJJ's Salesman dp+离散化 线段树优化

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) on the rectangle map and B (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) now (0≤x≤109,0≤y≤109) , he will only forward to (x+1,y) , (x,y+1) or (x+1,y+1) .
On the rectangle map from (0,0) to (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 village k on (xk,yk) (1≤xk≤109,1≤yk≤109) , only the one who was from (xk−1,yk−1) to (xk,yk) will be able to earn vk dollars.(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 integer T (1≤T≤10) ,which is the number of test cases.

In each case, the first line of the input contains an integer N (1≤N≤105) .The following N lines, the k -th line contains 3 integers, xk,yk,vk (0≤vk≤103) , which indicate that there is a village on (xk,yk) and he can get vk dollars in that village.
The positions of each village is distinct.

 

 

Output

The maximum of dollars YJJ can get.

 

 

Sample Input

1 3 1 1 1 1 2 2 3 3 1

 

 

Sample Output

3

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstdlib>
#include<cctype>
#include<deque>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f;
const int len=1e5+5;
struct pp{
	int x,y,w;
	bool operator<(pp a)const
	{if(x==a.x)return y>a.y;return x<a.x;}
	//因为只有斜着走才能获得金币，这样排序保证了当x相同时不能获得金币， 
}p[len];
int s[len*2];
struct Node{
	int l,r,maxx;
	int mid(){return (l+r)/2;}
}node[len*4];
void built(int i,int l,int r)
{
	node[i].l=l;node[i].r=r;
	node[i].maxx=0;
	if(l==r)return ;
	int mid=node[i].mid();
	built(i*2,l,mid);
	built(i*2+1,mid+1,r);
	node[i].maxx=max(node[i*2].maxx,node[i*2+1].maxx);
}
void update(int i,int x,int v)
{
	if(node[i].l==node[i].r&&node[i].l==x)
	{
		node[i].maxx=v;//注意这里是等于，而不是加v 
		return ;
	}
	int mid=node[i].mid();
	if(x<=mid)update(i*2,x,v);
	if(x>mid)update(i*2+1,x,v);
	node[i].maxx=max(node[i*2].maxx,node[i*2+1].maxx);
}
int query(int i,int l,int r)
{
	if(l<=node[i].l&&node[i].r<=r)return node[i].maxx;
	int mid=node[i].mid();int ans=0;
	if(l<=mid)ans=max(ans,query(i*2,l,r));
	if(r>mid)ans=max(ans,query(i*2+1,l,r));
	return ans;
} 
int dp[len];
//状态是从i列转移到i+1列 
//dp[i][j]表示在第i列第j行的最大前缀和,（获得的金币） 
int main() 
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		int n;
		scanf("%d",&n);
		int l=0;
		for(int i=0;i<n;++i)
		{
			scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
			s[l++]=p[i].x;
			s[l++]=p[i].y;
		}
		sort(s,s+l);
		l=unique(s,s+l)-s;
		for(int i=0;i<n;++i)
		{
			p[i].x=lower_bound(s,s+l,p[i].x)-s+1;
			p[i].y=lower_bound(s,s+l,p[i].y)-s+1;//离散化 
		}
		sort(p,p+n);
		built(1,1,l);
		for(int i=0;i<n;++i)
		{
			int temp=p[i].y;
			int x;//注意状态是由i行转移到i+1行的所以这种方法一定是可以从i-1，j-1到i，j的 
			if(temp==1)x=p[i].w;//当temp==1时，前0行最大值为0 
			else x=query(1,1,p[i].y-1)+p[i].w;//前temp-1行的最大值 
			dp[temp]=max(dp[temp],x);
			update(1,temp,dp[temp]);//在tmep行更新为最大值dp[temp]； 
		}
		int ans=0;
		for(int i=1;i<=l;++i)ans=max(ans,dp[i]); 
		//取每行的最大值 
		printf("%d\n",ans);
	}
}