HDU6447（离散化扫描线+树状数组）
几句话简谈题意：
YJJ要从（0，0）点走到（1e9，1e9），当他处于点（x，y）时他只能走到（x，y+1）或（x+1，y）或（x+1，y+1）。而坐标轴上有n个村庄，如果他路过某个村庄就会赚到特定数量的钱，可是处于点（xk，yk）的村庄只会跟从点（xk-1，yk-1）走过来的人交易。求YJJ走完旅途能得到的最大钱数。
（每步好几个可选、求最后的最大XX，一眼dp对吧）
输入格式：
第一行一个T（1 <= T <= 10），代表测试数据组数；
之后对于每组测试数据，第一行读入n（1 <= n <= 1e5），代表n个村庄；
接下来的n行每行三个数字x，y，value，表示这个村庄在点（x，y），如果你从（x-1，y-1）走过来的话就能和它做交易并得到value数量的钱。其中1 <= x, y <= 1e9，0 <= value <= 1e3。
输出格式：
每组数据一行一个数字，表示旅途走完后可以得到的最大钱数。
样例输入：
1
3
1 1 1
1 2 2
3 3 1
样例输出：
3
放这道题的本意：
上一期放了一个树状数组的题，但我觉得很可能有很多人并不会这个东西……然后这题作为一个小测试，上次不会的东西，回过头来自己找时间学了吗？有时候有缘遇到了不会的东西就不妨去学一学，否则下次遇到可能就是考场了。
一句话口胡题解：
还是一道比较常规的题目，大概会的人不用我讲，不会的人需要自学（啥玩意）。一些简单琐碎的点，不好讲。
一眼看过去就x排序扫描一下，y是1e9的离散化一下，每层用树状数组或者线段树维护一下，然后发现y正着扫不行对吧？像dp倒着循环似的树状数组把y倒着插就可行了。
然鹅这种意识流题解不可能看懂的……
自学标签：1.离散化；2.扫描线；3.树状数组；4.线段树（因为更常见的是用线段树维护）；5.背包（大雾。01背包使用一维滚动数组时为什么要倒着扫你真的懂了吗？）
学完以上几个以后可以尝试这道题目了，后续推荐练习：BZOJ4653、BZOJ1218.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <fstream>
#include <bitset>
#define init(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define irep(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18;
template <typename T> void read(T &x) {
x = 0;
int s = 1, c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') s = -1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
x *= s;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
const int maxn = 1e5 + 5;
int T, n;
struct cord {
int x, y, v;
bool operator < (const cord& rhs) const {
if (x != rhs.x) return x < rhs.x;
return y > rhs.y;
}
}a[maxn];
int yy[maxn], tot;
struct BIT {//树状数组
int F[maxn];
void Update(int pos, int val) {
for (; pos <= tot; pos += pos&-pos)
F[pos] = max(F[pos], val);
}
int Query(int pos) {
int ret = 0;
for (; pos; pos -= pos&-pos)
ret = max(ret, F[pos]);
return ret;
}
}bit;
int main() {
for (read(T); T; T--, tot = 0) {
read(n);
rep(i, 1, n) {
read(a[i].x);
read(a[i].y);
read(a[i].v);
yy[++tot] = a[i].y;
}
//离散化
sort(yy + 1, yy + 1 + tot);
tot = unique(yy + 1, yy + 1 + tot) - yy - 1;
rep(i, 1, n) {
a[i].y = lower_bound(yy + 1, yy + 1 + tot, a[i].y) - yy;
}
//扫描插入，注意a的排序
sort(a + 1, a + 1 + n);
init(bit.F, 0);
rep(i, 1, n) {
bit.Update(a[i].y, bit.Query(a[i].y - 1) + a[i].v);
}
writeln(bit.Query(tot));
}
return 0;
}腾讯云开发者
