【题目链接】

题目意思

T组案例，给一个n，下面n行，每行三个数字(x,y,v)表示点（x,y）处的值为v，只有当从(x-1,y-1)走到(x,y)时，才能获得点(x,y)的v值，求从(0,0)走到(1e9,1e9)时的最大收获值。

Sample Input
1
3
1 1 1
1 2 2
3 3 1
Sample Output
3

解题思路

离散化+树状数组维护区间最大值，首先看到题目肯定想到简单dp，无奈数据量实在太大了，遍历O(n)都会超时的那种，因为n<100 000，所以想到离散化，将n的坐标离散化处理，使其均小于等于100 000，然后排序用01背包的思路，对于每一维的x，对y按照从大到小维护(1-100 000)区间最大值，最后区间内最大值即为所求答案，时间复杂度O(nlogn)。

AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int maxx[100005], a[100005];
struct node
{
    int x, y, v;
};
node que[100005];
int lowbit(int k)
{
    return k & (-k);
}
void update(int k, int x)
{
    while (k <= 100005)
    {
        maxx[k] = max(maxx[k], x);
        k += lowbit(k);
    }
}
int query(int k)
{
    int ans = 0;
    while (k > 0)
    {
        ans = max(ans, maxx[k]);
        k -= lowbit(k);
    }
    return ans;
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        memset(maxx, 0, sizeof maxx);
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &que[i].x, &que[i].y, &que[i].v);
            a[i] = que[i].y;
        }
        //离散化纵坐标
        sort(a, a + n);
        int all = unique(a, a + n) - a;
        for (int i = 0; i < n; i++)
            que[i].y = lower_bound(a, a + all, que[i].y) - a + 1;
        //排序
        sort(que, que + n, [](node a, node b)
        {
            if (a.x == b.x)
                return a.y > b.y;
            else
                return a.x < b.x;
        });
        //维护区间最大值
        for (int i = 0; i < n; i++)
        {
            int val = query(que[i].y - 1) + que[i].v;
            update(que[i].y, val);
        }
        printf("%d\n", query(100005));
    }
}