GYM101899F-Fundraising(二维偏序)

题目链接:GYM101899F-Fundraising

题意:

有n个物品,每个物品有两个参数,并且有一个价值,然后可以从中选取一些物品,要求这些物品中的任意两个物品中一个物品的两个参数均大于另一个物品,或者两个物品的参数完全相等。

题解:

严格大于的二维偏序。

首先将完全相等的物品缩点,然后二维偏序即可,注意排序时,第一维递增第二维递减,可保证严格大于。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int inf = 0x3f3f3f3f;
int n;
struct NODE
{
    int x, y;
    ll val;
    NODE() {}
    NODE(int x, int y, ll val)
    {
        this->x = x, this->y = y, this->val = val;
    }
} a[MAXN];
int Y[MAXN];
struct BIT
{
    ll c[MAXN];
    int n;
    void init(int n)
    {
        for (int i = 1; i <= n; i++)
            c[i] = 0;
        this->n = n;
    }
    int lowbit(int x)
    {
        return x & -x;
    }
    void update(int x, ll val)
    {
        while (x <= n)
        {
            c[x] = max(c[x], val);
            x += lowbit(x);
        }
    }
    ll query_max(int x)
    {
        ll ret = 0ll;
        while (x)
        {
            ret = max(ret, c[x]);
            x -= lowbit(x);
        }
        return ret;
    }
} bit;
map<pair<int, int>, ll> mp;
int main()
{
    scanf("%d", &n);
    mp.clear();
    int tot = 0;
    for (int i = 1; i <= n; i++)
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        if (mp.count({x, y}))
            mp[{x, y}] += 1ll * w;
        else
            mp[{x, y}] = 1ll * w;
        Y[i] = y;
    }
    sort(Y + 1, Y + 1 + n);
    int Ycnt = unique(Y + 1, Y + 1 + n) - Y;
    for (auto v : mp)
        a[++tot] = NODE(v.first.first, v.first.second, v.second);
    sort(a + 1, a + 1 + tot, [](NODE x, NODE y) { return (x.x == y.x) ? x.y > y.y : x.x < y.x; });
    for (int i = 1; i <= tot; i++)
        a[i].y = lower_bound(Y + 1, Y + 1 + Ycnt, a[i].y) - Y + 1;
    bit.init(Ycnt);
    ll ans = 0;
    for (int i = 1; i <= tot; i++)
    {
        ll res = bit.query_max(a[i].y - 1) + a[i].val;
        ans = max(ans, res);
        bit.update(a[i].y, res);
    }
    printf("%lld\n", ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。