HDU 6447 YJJ's Salesman(离散化＋线段树＋动态规划)

Description:

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination. One day, he is going to travel from city A to southeastern city B. Let us assume that A is (0,0) on the rectangle map and B (109,109). YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at (x,y) now (0≤x≤109,0≤y≤109), he will only forward to (x+1,y), (x,y+1) or (x+1,y+1). On the rectangle map from (0,0) to (109,109), there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a village k on (xk,yk) (1≤xk≤109,1≤yk≤109), only the one who was from (xk−1,yk−1) to (xk,yk) will be able to earn vk dollars.(YJJ may get different number of dollars from different village.) YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.

Input:

The first line of the input contains an integer T (1≤T≤10),which is the number of test cases. In each case, the first line of the input contains an integer N (1≤N≤105).The following N lines, the k-th line contains 3 integers, xk,yk,vk (0≤vk≤103), which indicate that there is a village on (xk,yk) and he can get vk dollars in that village. The positions of each village is distinct.

Output:

The maximum of dollars YJJ can get.

Sample Input:

1
3
1 1 1
1 2 2
3 3 1

Sample Output:

题目链接

题目数据范围很大，最大能够达到 $1 0^{9} \times 1 0^{9}$ 的矩阵大小，但是由于只进行最大 $1 0^{5}$ 的输入，所以矩阵的宽和高最多有 $1 0^{5}$ 个数据，因此进行离散化将 $1 0^{9} \times 1 0^{9}$ 的矩阵大小离散到 $1 0^{5} \times 1 0^{5}$ 的矩阵大小范围上，由于[1e5][1e5]大小的二维矩阵数组也开不出来，所以我们按行进行每列更新dp数组的值

$d p [i] = m a x (Q u e r y_M a x (0, d p [i] - 1, 1) + v a l [i], d p [i])$

$P o i n t U p d a t e (i, d p [i], 1)$

按01背包的更新顺序，滚动数组优化dp到1维。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

struct Node {
    int Left, Right, Max;
    Node(int _Left = 0, int _Right = 0, int _Max = 0): Left(_Left), Right(_Right), Max(_Max) {}
};

Node SegmentTree[maxn << 2];

void Build(int Left, int Right, int Root) {
    SegmentTree[Root].Left = Left;
    SegmentTree[Root].Right = Right;
    SegmentTree[Root].Max = 0;
    if (Left == Right) {
        return;
    }
    int Mid = (Left + Right) >> 1;
    Build(Left, Mid, Root << 1);
    Build(Mid + 1, Right, Root << 1 | 1);
    SegmentTree[Root].Max = max(SegmentTree[Root << 1].Max, SegmentTree[Root << 1 | 1].Max);
}

void PointUpdate(int Pos, int Value, int Root) {
    if (SegmentTree[Root].Left == Pos && SegmentTree[Root].Right == Pos) {
        SegmentTree[Root].Max = Value;
        return;
    }
    int Mid = (SegmentTree[Root].Left + SegmentTree[Root].Right) >> 1;
    if (Pos <= Mid) {
        PointUpdate(Pos, Value, Root << 1);
    }
    else {
        PointUpdate(Pos, Value, Root << 1 | 1);
    }
    SegmentTree[Root].Max = max(SegmentTree[Root << 1].Max, SegmentTree[Root << 1 | 1].Max);
}

int Query(int Left, int Right, int Root) {
    if (Left == SegmentTree[Root].Left && Right == SegmentTree[Root].Right) {
        return SegmentTree[Root].Max;
    }
    int Mid = (SegmentTree[Root].Left + SegmentTree[Root].Right) >> 1;
    if (Right <= Mid) {
        return Query(Left, Right, Root << 1);
    }
    else if (Left > Mid) {
        return Query(Left, Right, Root << 1 | 1);
    }
    else {
        return max(Query(Left, Mid, Root << 1), Query(Mid + 1, Right, Root << 1 | 1));
    }
}

struct Point {
    int X, Y, Weight;
    Point(int _X = 0, int _Y = 0, int _Weight = 0): X(_X), Y(_Y), Weight(_Weight) {}
};

int T;
int N;
int Ans;
int PosX[maxn], PosY[maxn];
int Dp[maxn];
Point points[maxn];

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d", &N);
        for (int i = 0; i < N; ++i) {
            scanf("%d%d%d", &points[i].X, &points[i].Y, &points[i].Weight);
            PosX[i] = points[i].X;
            PosY[i] = points[i].Y;
        }
        // 离散化
        PosX[N] = 0; PosY[N] = 0;
        sort(PosX, PosX + N + 1);
        sort(PosY, PosY + N + 1);
        int XNum = unique(PosX, PosX + N + 1) - PosX;
        int YNum = unique(PosY, PosY + N + 1) - PosY;
        for (int i = 0; i < N; ++i) {
            points[i].X = lower_bound(PosX, PosX + XNum, points[i].X) - PosX;
            points[i].Y = lower_bound(PosY, PosY + YNum, points[i].Y) - PosY;
        }
        sort(points, points + N, [&] (const Point &a, const Point &b) {
                if (a.X == b.X) {
                    return a.Y > b.Y;
                }
                return a.X < b.X;
        });
        Build(0, YNum, 1);
        memset(Dp, 0, sizeof(Dp));
        // 根据线段数按行更新Dp数组和线段树
        for (int i = 0; i < N; ++i) {
            int Flag = points[i].X, j;
            for (j = i; j < N; ++j) {
                if (points[j].X != Flag) {
                    break;
                }
                int Temp = Query(0, points[j].Y - 1, 1) + points[j].Weight;
                if (Temp > Dp[points[j].Y]) {
                    Dp[points[j].Y] = Temp;
                    PointUpdate(points[j].Y, Dp[points[j].Y], 1);
                }
            }
            i = j - 1;
        }
        Ans = 0;
        for (int i = 0; i <= YNum; ++i) {
            Ans = max(Ans, Dp[i]);
        }
        printf("%d\n", Ans);
    }
    return 0;
}