P3431 [POI2005]AUT-The Bus

P3431 [POI2005]AUT-The Bus
题意
给你一个n×m的网格，告诉你了k个网格中的信息，(x,y)这个位置有p个人，现在有一辆公交这在(1, 1)，它只能向右或者向上走，最终会走到终点，问你最后可能载多少人。
思路
离散化+DP+树状数组
离散化：首先观察给你的n和m的范围：$1\le n\le 10^9$，m的范围也是这样，所以我们想到了离散化，将坐标离散。
DP：公交车在走的时候肯定是从近走到远，那么对于我们要走到的位置，我们肯定要进行排序，我们不妨将x作为第一关键字进行排序，而y作为第二关键字进行排序，假设我们现在走到了k个点中的第i个点，那么f[i] = max(a[i].y) + a[i].num，这里表示前面接到的人数加上当前位置的人数，然后这里在找max(a[i].y)的时候，物品们可以用树状数组来进行维护。
树状数组：我们上面知道了，维护max(a[i].y)可以采用树状数组来进行维护，那么我们树状数组记录的就是最大值了，而不是前缀和了。
ps：这里为什么f[k]不是最大值呢？首先，我们最终是要到达(n, m)这个点的，但是f[k]不一定是终点。但是我们最终都是要到达终点的。

    #include 

    using namespace std;

    const int N = 500005;

    int n, m, k;
    int nx, ny;
    int tr[N * 4];
    int f[N];
    int x[N], y[N];
    map<int, int> mpx, mpy;

    struct node
    {
        int x, y, num;
        bool operator < (const node & t) const
        {
            return x == t.x ? y < t.y : x < t.x;
        }
    }a[N];

    int lowbit(int x) { return x & -x; }

    void add(int x, int k) { for (int i = x; i <= N; i += lowbit(i)) tr[i] = max(tr[i], k); }

    int sum(int x)
    {
        int ans = 0;
        for (int i = x; i ; i -= lowbit(i)) ans = max(ans, tr[i]);
        return ans;
    }

    void solve()
    {
        cin >> n >> m >> k;
        for (int i = 1; i <= k; i ++)
        {
            cin >> a[i].x >> a[i].y >> a[i].num;
            x[i] = a[i].x, y[i] = a[i].y;
        }

        x[0] = y[0] = 1;
        sort(x, x + 1 + k), sort(y, y + 1 + k);
        mpx[x[0]] = ++nx, mpy[y[0]] = ++ny;

        for (int i = 1; i <= k; i ++)
        {
            if (x[i] != x[i - 1]) mpx[x[i]] = ++ nx;
            if (y[i] != y[i - 1]) mpy[y[i]] = ++ ny;
        }

        for (int i = 1; i <= k; i ++)
            a[i].x = mpx[a[i].x], a[i].y = mpy[a[i].y];

        sort(a +1, a + 1 + k);

        for (int i = 1; i <= k; i ++)
        {
            f[i] = sum(a[i].y) + a[i].num;
            add(a[i].y, f[i]);
        }

        int ans = 0 ;
        for (int i = 1; i <= k; i ++) ans = max(ans,f[i]);

        cout << ans << endl;
    }

    signed main()
    {
        std::ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        solve();

        return 0;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80