Luogu3431 [POI2005]AUT-The Bus

发布于 2019-11-13  124 次阅读


Link

题意

要求从 (1,1) 走到 (n, m) ,可以走上下左右四个方向。要求中间经过一些点,使得走过的点加起来的权值最大。

题解

这道题是我用来练习二维偏序的(只有我这个菜鸡要学二维偏序

但是看到题目很自然地先考虑DP。朴素地,设 f[i] 表示走到第 i 个点的最大值,那么我们有:f[i] = max{f[j]+w[i]} , 其中x[j] \leq x[i]y[j] \leq y[i]

那么这样DP是 O(n^2) 的(这道题是 k ),显然无法承受。

简单观察出:x[j] \leq x[i]y[j] \leq y[i],这个东西基本上就是二维偏序的条件。

具体地说,假如我们现在要二维扫点(统计某个点左下方有多少个点),可以这么做:

首先对横/纵坐标排序(以纵坐标为例),现在我们已知当前坐标数组左侧的点一定纵坐标小于当前点,只需要统计横坐标小于它的即可。这个过程可以用树状数组实现。

所以这道题就变成了一个二维偏序的入门题,我们统计一个前缀并取max即可。

注意x\leq y\leq10^9 , 而实际只有 k\leq10^5 个点,直接存储空间无法接受,需要离散化。

Code

#include 
using namespace std;

const int SIZE = 100000 + 5;

int n, m, k;
int c[SIZE], bit[SIZE];

struct node {
    int x, y, p;
    inline bool operator < (const node a) const {
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
} a[SIZE]; 

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

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

inline int Query(int x)
{
    int ans = 0;
    for ( ; x; x -= lowbit(x)) ans = std::max(ans, bit[x]);
    return ans;
}

inline void Change(int x, int val)
{
    for ( ; x <= k; x += lowbit(x)) bit[x] = std::max(bit[x], val);
}

signed main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    n = read(), m = read(), k = read();
    for (int i = 1; i <= k; i++) {
        a[i].x = read(), a[i].y = read(), a[i].p = read();
        c[i] = a[i].y;
    }
    std::sort(c + 1, c + k + 1);
    m = std::unique(c + 1, c + k + 1) - c - 1;
    for (int i = 1; i <= k; i++) a[i].y = lower_bound(c + 1, c + m + 1, a[i].y) - c;
    std::sort(a + 1, a + k + 1);
    int ans = 0;
    for (int i = 1; i <= k; i++) {
        int sum = Query(a[i].y) + a[i].p;
        ans = std::max(ans, sum);
        Change(a[i].y, sum);
    }
    printf("%lld", ans);
    return 0;
}

苟利国家生死以,岂因祸福避趋之.