题意：

n个点，分成两组A，B，如果点i在A中，那么贡献值\(a_i\)，反之为\(b_i\)。

现要求任意\(i \in A，j \in B\)不存在 \(x_i >= x_j\) 且 \(y_i <= y_j\)，也就是说A中点不在B中点的右下方。

思路：

https://blog.nowcoder.net/n/7205418146f3446eb0b1ecec8d2ab1da

代码：

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 1e5 + 5;

const int M = 50 + 5;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 1000000007;

struct Node{

    int x, y, a, b;

}p[maxn];

bool cmp(Node x, Node y){

    if(x.x == y.x) return x.y > y.y;

    return x.x < y.x;

}

vector<int> vv;

ll Max[maxn << 2], lazy[maxn << 2];

void pushup(int rt){

    Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);

}

void pushdown(int rt){

    if(lazy[rt]){

        lazy[rt << 1] += lazy[rt];

        lazy[rt << 1 | 1] += lazy[rt];

        Max[rt << 1] += lazy[rt];

        Max[rt << 1 | 1] += lazy[rt];

        lazy[rt] = 0;

    }

}

void build(int l, int r, int rt){

    Max[rt] = lazy[rt] = 0;

    if(l == r) return;

    int m = (l + r) >> 1;

    build(l, m, rt << 1);

    build(m + 1, r, rt << 1 | 1);

}

void update(int L, int R, int l, int r, int v, int rt){

    if(L > R) return;

    if(L <= l && R >= r){

        Max[rt] += v;

        lazy[rt] += v;

        return;

    }

    pushdown(rt);

    int m = (l + r) >> 1;

    if(L <= m)

        update(L, R, l, m, v, rt << 1);

    if(R > m)

        update(L, R, m + 1, r, v, rt << 1 | 1);

    pushup(rt);

}

void change(int pos , int l, int r, ll v, int rt){

    if(l == r){

        Max[rt] = max(Max[rt], v);

        return;

    }

    pushdown(rt);

    int m = (l + r) >> 1;

    if(pos <= m)

        change(pos, l, m, v, rt << 1);

    else

        change(pos, m + 1, r, v, rt << 1 | 1);

    pushup(rt);

}

ll query(int L, int R, int l, int r, int rt){

    if(L <= l && R >= r){

        return Max[rt];

    }

    pushdown(rt);

    int m = (l + r) >> 1;

    ll MAX = -1;

    if(L <= m)

        MAX = max(MAX, query(L, R, l, m, rt << 1));

    if(R > m)

        MAX = max(MAX, query(L, R, m + 1, r, rt << 1 | 1));

    pushup(rt);

    return MAX;

}

int main(){

    int n;

    while(~scanf("%d", &n)){

        vv.clear();

        for(int i = 1; i <= n; i++){

            scanf("%d%d%d%d", &p[i].x, &p[i].y, &p[i].a, &p[i].b);

            vv.push_back(p[i].y);

        }

        vv.push_back(-1);

        sort(vv.begin(), vv.end());

        vv.erase(unique(vv.begin(), vv.end()), vv.end());

        for(int i = 1; i <= n; i++) p[i].y = lower_bound(vv.begin(), vv.end(), p[i].y) - vv.begin() + 1;

        sort(p + 1, p + n + 1, cmp);

        build(1, vv.size(), 1);

        for(int i = 1; i <= n; i++){

            ll tmp = query(1, p[i].y, 1, vv.size(), 1);

            update(p[i].y, vv.size(), 1, vv.size(), p[i].b, 1);

            update(1, p[i].y - 1, 1, vv.size(), p[i].a, 1);

            change(p[i].y, 1, vv.size(), tmp + p[i].b, 1);

        }

        printf("%lld\n", Max[1]);

    }

    return 0;

}

巴特西

2019牛客多校第一场I Points Division（DP）题解

题意：

思路：

代码：

最新文章

热门文章