Luogu P7842 「C.E.L.U-03」探险者笔记 III

题目描述

https://www.luogu.com.cn/problem/P7842

简要题意：给定 $n$ 个物品和 $m$ 个属性以及常数 $w$，第 $i$ 个物品有一个价值 $c_i$ 以及其所拥有的属性 $S_i$，现在要依次选择若干个物品，满足相邻两个物品 $i$ 和 $j$ 满足 $i<j\wedge w+c_i\ge c_j\wedge S_i\subseteq S_j$，求最多选择多少个物品

$n\le 10^5,m\le 18$

Solution

首先考虑 $cdq$ 分治解决第一个和第二个限制，对于第三个限制，我们考虑每次 $cdq$ 分治的时候将左部的每个点都贡献到自己的超集，这样可以做到 $O(2^m)$ 预处理，$O(1)$ 查询，或者我们考虑用右部的每个点求子集查询，这样是 $O(1)$ 预处理，$O(2^m)$ 查询，我们可以平衡一下，前 $\frac m 2$ 位贡献到超集，后 $\frac m 2 $ 子集查询，这样做的时间复杂度为 $O(2^{\frac m 2}n\log n+n\log^2 n)$

#include <iostream>
#include <algorithm>
#define maxn 300010
#define maxm 512
using namespace std;

const int M = 511;
const int N = 9;

int n, m, w, b[maxn];

struct node {
    int v, k, s1, s2, id;

    friend bool operator < (const node &u, const node &v) { return u.v > v.v; } 
} a[maxn]; 

int ans[maxn], mx[maxm][maxm];
void cdq(int l, int r) {
    if (l == r) return ans[a[l].id] = max(ans[a[l].id], a[l].k), void();
    int m = l + r >> 1; cdq(l, m);
    sort(a + l, a + m + 1); sort(a + m + 1, a + r + 1); 
    for (int i = m + 1, j = l; i <= r; ++i) {
        while (j <= m && w + a[j].v >= a[i].v) {
            for (int S = a[j].s1; S != M; S = S + 1 | a[j].s1)
                mx[S][a[j].s2] = max(mx[S][a[j].s2], ans[a[j].id]);
            mx[M][a[j].s2] = max(mx[M][a[j].s2], ans[a[j].id]); 
            ++j;
        } 
        for (int S = a[i].s2; S; S = S - 1 & a[i].s2)
            ans[a[i].id] = max(ans[a[i].id], mx[a[i].s1][S] + a[i].k);
        ans[a[i].id] = max(ans[a[i].id], mx[a[i].s1][0] + a[i].k);
    }
    for (int i = l; i <= m; ++i) { 
        for (int S = a[i].s1; S != M; S = S + 1 | a[i].s1) mx[S][a[i].s2] = 0;
        mx[M][a[i].s2] = 0;
    } sort(a + m + 1, a + r + 1, [](const node &u, const node &v) { return u.id < v.id; });
    cdq(m + 1, r); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> m >> n >> w; 
    for (int i = 1; i <= m; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i) {
        int l, S = 0; cin >> a[i].k >> l;
        for (int j = 1, x; j <= l; ++j) cin >> x, S |= 1 << x - 1, a[i].v += b[x];
        a[i].s1 = S & M; a[i].s2 = S >> N; a[i].id = i; 
    } cdq(1, n); cout << *max_element(ans + 1, ans + n + 1) << "\n";
    return 0;
}