11
显然的DP，设$f[i]$表示最后一个接了第$i$个车站的最多接的人数。
然后$f[i] = max(f[j]) + p[i]$，$j$满足$x[j] \leq x[i]$ and $y[j] \leq y[i]$.
于是我们可以把坐标按$x$轴从小到大排序，$x$相同按$j$从小到大排序，因为我们在更新$y$更大的时候的答案的时候可能从$y$更小的转移过来。
我们已经保证了所有的可能转移过来的$j$的$x[j]$是小于等于$x[i]$的， 我们只要保证$y[j] \leq y[i]$就行了。
这样我们可以用树状数组维护纵坐标小于等于$y[i]$的最大值。
对了坐标值的范围太大需要把纵坐标离散化。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; #define reg register inline char gc() { static const int bs = 1 << 22; static unsigned char buf[bs], *st, *ed; if (st == ed) ed = buf + fread(st = buf, 1, bs, stdin); return st == ed ? EOF : *st++; } #define gc getchar inline int read() { int res=0;char ch=gc();bool fu=0; while(!isdigit(ch))fu|=(ch==‘-‘), ch=gc(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48), ch=gc(); return fu?-res:res; } #define N 1000005 int n, m, K; int ans; struct date { int x, y, p; bool operator < (const date a) const { if (x == a.x) return y < a.y; return x < a.x; } }da[N]; int f[N]; int tr[N]; int cpy[N], u; inline void change(int x, int y) { while(x <= u) { tr[x] = max(tr[x], y); x += x & -x; } } inline int query(int x) { int res = 0; while(x) { res = max(res, tr[x]); x -= x & -x; } return res; } int main() { n = read(), m = read(), K = read(); for (reg int i = 1, t ; i <= K ; i ++) da[i] = (date){read(), t = read(), read()}, cpy[i] = t; sort(cpy + 1, cpy + 1 + K); u = unique(cpy + 1, cpy + 1 + K) - cpy - 1; for (reg int i = 1 ; i <= K ; i ++) da[i].y = lower_bound(cpy + 1, cpy + 1 + u, da[i].y) - cpy; sort(da + 1, da + 1 + K); for (reg int i = 1 ; i <= K ; i ++) { f[i] = query(da[i].y) + da[i].p; change(da[i].y, f[i]); ans = max(ans, f[i]); } cout << ans << endl; return 0; }
[BZOJ1537][POI2005]Aut- The Bus
原文：https://www.cnblogs.com/BriMon/p/9763699.html