HDU6447 YJJ's Salesman

骑猪看日落 2021-11-08 17:31 118阅读 0赞

# 树状数组 + 离散化 #

把坐标按y从小到大排序，y相同的按x从大到小排序，然后把x离散化以后用树状数组维护前缀最大值。（并不是严格的前缀最大值，对于之前树状数组中的最值，如果修改的值小于原值，仍然把原来的值当成最大值），就相当于选择了之前的点做转移。

这样保证了每次更新时，当前点一定是由左下方的矩阵转移而来。x要从小到大排序是因为保证每次更新对于y相同的点不会被其左边的点影响。

#include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    #define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
    using namespace std;
    typedef long long ll;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int ret = 0, w = 0; char ch = 0;
        while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
        while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = getchar();
        return w ? -ret : ret;
    }
    inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
    inline int lcm(int a, int b){ return a / gcd(a, b) * b; }
    template <typename T>
    inline T max(T x, T y, T z){ return max(max(x, y), z); }
    template <typename T>
    inline T min(T x, T y, T z){ return min(min(x, y), z); }
    template <typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 200005;
    int _, n, tot, a[N], tree[N], ans;
    struct Pos{
        int x, y, w;
        bool operator < (const Pos &rhs) const {
            if(y != rhs.y) return y < rhs.y;
            return x > rhs.x;
        }
    }pos[N];
    
    inline void add(int k, int val){
        for(; k <= n; k += lowbit(k)) tree[k] = max(val, tree[k]);
    }
    
    inline int query(int k){
        int ret = 0;
        for(; k; k -= lowbit(k)) ret = max(ret, tree[k]);
        return ret;
    }
    
    int main(){
    
        for(_ = read(); _; _ --){
            n = read(), ans = 0;
            full(a, 0), full(tree, 0);
            for(int i = 1; i <= n; i ++){
                pos[i].x = read(), pos[i].y = read(), pos[i].w = read();
                a[++tot] = pos[i].x;
            }
            sort(pos + 1, pos + n + 1);
            sort(a + 1, a + tot + 1);
            tot = unique(a + 1, a + tot + 1) - a - 1;
            for(int i = 1; i <= n; i ++){
                int p = lower_bound(a + 1, a + tot + 1, pos[i].x) - a;
                int val = query(p - 1) + pos[i].w;
                ans = max(ans, val);
                add(p, val);
            }
            printf("%d\n", ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/onionQAQ/p/11178429.html