题目描述：P3431 [POI2005]AUT-The Bus 该题二维坐标分布广，且点稀疏，所以对点坐标进行离散化，二维坐标离散化（蒟蒻） 利用树状数组的动态维护区间的特性，进行动态规划 DP+树状数组 核心代码：
for(int i = 1; i <= k; i++){ // 能走到f[i].y 的最大值 与 f[i].k的值和作为 dp[ i ]的值 dp[i] = ask( f[i].y) + f[i].k; // 由于 f[ i ]点的加入，更新右边的dp[ ] updata(f[i].y, dp[i]); }下图与核心代码搭配食用 dp[ ] 就相当于 t[ ]，通过树状数组维护
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int n, m, k, ans; int x[maxn], y[maxn], val[maxn]; int nx[maxn*2], ny[maxn*2], tot1 = 1, tot2 = 1; int t[maxn*2], dp[maxn*2]; struct node { int x, y, k; }f[maxn], a[maxn]; bool cmp(const node &aa, const node &bb){ return (aa.x==bb.x?aa.y<bb.y:aa.x<bb.x); } void updata(int x, int k){ for( ; x <= tot2; x += x&-x){ t[x] = max(t[x], k); } } int ask(int x){ int maxx = 0; for( ; x; x -= x&-x){ maxx = max(t[x], maxx); } return maxx; } int main(){ cin >> n >> m >> k; for(int i = 1; i <= k; i++){ cin >> x[i] >> y[i] >> a[i].k; a[i].x = x[i], a[i].y = y[i]; } a[k + 1].x = n, a[k + 1].y = m, a[k + 1].k = 0; // 离散化 x[0] = 1, y[0] = 1; x[k + 1] = n, y[k + 1] = m; // 排序 sort(x, x + k + 2); sort(y, y + k + 2); // 去重 和 不重复数组长度 int len1 = unique(x, x + k + 2) - x; int len2 = unique(y, y + k + 2) - y; // 离散化 x 轴 for(int i = 0; i < len1; i++){ if(i && x[i] != x[i - 1] + 1) nx[tot1++] = x[i] - 1, nx[tot1++] = x[i]; else nx[tot1++] = x[i]; } // 离散化 y 轴 for(int i = 0; i < len2; i++){ if(i && y[i] != y[i - 1] + 1) ny[tot2++] = y[i] - 1, ny[tot2++] = y[i]; else ny[tot2++] = y[i]; } // 得到离散化后的坐标 for(int i = 1; i <= k + 1; i++){ int newx = lower_bound(nx, nx + tot1 + 1, a[i].x) - nx; int newy = lower_bound(ny, ny + tot2 + 1, a[i].y) - ny; f[i].x = newx, f[i].y = newy, f[i].k = a[i].k; } // 以 x 轴为第一关键字，y 轴为第二关键字 进行排列 sort(f + 1, f + k + 1, cmp); // dp + 树状数组 for(int i = 1; i <= k; i++){ dp[i] = ask( f[i].y) + f[i].k; updata(f[i].y, dp[i]); } for(int i = 1; i <= k; i++) ans = max(ans, dp[i]); cout << ans << endl; return 0; }