思路：若用dp[i][j]表示走到（i，j）的最大值，那么dp[i][j] = max(dp[i - 1][j]，dp[i][j - 1]，dp[i - 1][j - 1] + v)，显然O（n^2）超时。但是我们可以优化这个dp，我们用f[j]表示第i行第j列当前最大值，那么f[j] = max(f[j]，f[k] + v[i][j])，k范围0~j - 1，所以我们只要用O（logn）找到f[k]就行了，显然可以用线段树维护f[j]。我们先离散化，然后从上到下，从右到左排序，从右到左是因为我们在更新第i行第j列时，我们所需要的f[k]是第i-1行以前的f[k]，这里需要注意。
代码：
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = + ;
const int seed = ;
const int MOD = ;
const int INF = 0x3f3f3f3f;
struct node{
int x, y, v;
}q[maxn];
bool cmp(node a, node b){
if(a.x < b.x) return true;
if(a.x == b.x && a.y > b.y) return true;
return false;
} int Max[maxn << ];
void update(int l, int r, int pos, int v, int rt){
if(l == r){
Max[rt] = max(Max[rt], v);
return;
}
int m = (l + r) >> ;
if(pos <= m)
update(l, m, pos, v, rt << );
else
update(m + , r, pos, v, rt << | );
Max[rt] = max(Max[rt << ], Max[rt << | ]);
}
int query(int l, int r, int L, int R, int rt){
if(L <= l && R >= r){
return Max[rt];
}
int MAX = ;
int m = (l + r) >> ;
if(L <= m)
MAX = max(MAX, query(l, m, L, R, rt << ));
if(R > m)
MAX = max(MAX, query(m + , r, L, R, rt << | ));
return MAX;
}
int x[maxn], y[maxn], f[maxn];
int main(){
int T, n;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = ; i < n; i++){
scanf("%d%d%d", &x[i], &y[i], &q[i].v);
q[i].x = x[i];
q[i].y = y[i];
}
sort(x, x + n);
sort(y, y + n);
int cnt1 = unique(x, x + n) - x;
int cnt2 = unique(y, y + n) - y;
for(int i = ; i < n; i++){
q[i].x = lower_bound(x, x + cnt1, q[i].x) - x + ;
q[i].y = lower_bound(y, y + cnt2, q[i].y) - y + ;
}
sort(q, q + n, cmp); memset(Max, , sizeof(Max));
for(int i = ; i < n; i++){
int ret;
if(q[i].y == ){
ret = q[i].v;
}
else{
ret = query(, cnt2, , q[i].y - , ) + q[i].v;
}
update(, cnt2, q[i].y, ret, );
}
printf("%d\n", Max[]);
}
return ;
}