HDU6447 YJJ's Salesman(2018CCPC网络赛,线段树，思路)
Problem Description
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 1Sample Output
3思路
先说题意，有个村庄，这些村庄的坐标范围在的范围内,每个村庄有一个权值。刚开始在坐标处，现在你可以向右走，向下走，向右下走，但是向右走和向下走都不得分，向右下走可以获得和当前村庄权值一样的分数，问最后能获得的权值的最大值是多少?
假设当前数据范围很小，我们很容易想到dp的方法,状态转移方程为:,但是很明显，这样做不符合数据范围要求。我们想一想如何优化，每一个点的坐标都是由他的左上位置的状态来转移过来的。
假设当前点的坐标为，那么能给当前点产生贡献的点的范围就是[1,x-1],的范围是[1,y-1]。
我们这个时候可以固定一个坐标轴，比如是轴，先对每个点的坐标从小到大进行排序，当横坐标相同时，按照纵坐标从大到小排序。这个时候我们只需要利用线段树维护一下每个点的纵坐标，定义是这个点能获得的最大权值,按照排序的顺序，先查询里面的最大值，然后当前点的最大权值就是查询的最大值+当前点的权值。
只需要每个点的最大值中取一个最大的值就是答案，因为数据范围较大，所以线段树需要离散化.
代码
#include <bits/stdc++.h>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int N = 1e5 + 10;
int n;
int X[N], MAX[N << 2], dp[N];
struct node
{
int x, y, v;
} a[N];
void pushup(int rt)
{
MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
if (l == r)
{
MAX[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushup(rt);
}
void update(int p, int c, int l, int r, int rt)
{
if (l == r)
{
MAX[rt] = c;
return;
}
int m = (l + r) >> 1;
if (p <= m)
update(p, c, lson);
else
update(p, c, rson);
pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
if (L <= l && r <= R)
return MAX[rt];
int m = (l + r) >> 1;
int ans = 0;
if (L <= m)
ans = max(ans, query(L, R, lson));
if (R > m)
ans = max(ans, query(L, R, rson));
return ans;
}
bool cmp(node A, node B)
{
if (A.x == B.x)
return A.y > B.y;
return A.x < B.x;
}
void solve()
{
int num = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].v);
X[num++] = a[i].y;
}
sort(a + 1, a + n + 1, cmp);
sort(X, X + num);
int m = unique(X, X + num) - X;
build(1, m, 1);
int maxx = 0;
for (int i = 1; i <= n; i++)
{
int pos = lower_bound(X, X + m, a[i].y) - X;
pos++;
if (pos > 1)
{
int tmp = query(1, pos - 1, 1, m, 1);
dp[i] = tmp + a[i].v;
update(pos, dp[i], 1, m, 1);
}
else
{
dp[i] = a[i].v;
update(pos, dp[i], 1, m, 1);
}
maxx = max(maxx, dp[i]);
}
printf("%d\n", maxx);
}
int main()
{
//freopen("in.txt", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
solve();
return 0;
}