11.20 C 盲盒流水线
题解 ： 盲盒流水线link
给定 \(n\) 个物品，每个物品有价值和质量，\(q\) 次询问，在 \(\) 中选质量不超过 \(m\) 的物品，每个物品至多选一次，并且要让价值最大
$ 1 \leq n \leq 20000$
$ 1 \leq m_i \leq 500$
$ 1 \leq q \leq 100000$
第一眼，这不是背包吗？
暴力：\(O(nmq)\) \(49pts\)
const int N = 2e4 + 20, mod = 998244353;int n, v, w, q, g, f, p;signed main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n; for(int i = 1; i > v >> w; cin >> q; for(int qwq = 1, l, r, m, cnt = 0; qwq > l >> r >> m; g = 1; for(int i = l; i = w; --j){ if(f < f] + v)f = f] + v, g = g] % mod ; else if(f == f] + v)f = f] + v, (g += g]) %= mod; } } for(int i = 1; i > qwq; B = n / (sqrt(qwq) + 1) + 1, cnt = n / B; for(int i = 1; ir_ >> m_; if(bel == bel){ g = 1;int as = 0, zz = 0; for(int i = l_; i = w; --j){ if(f < f] + v)f = f] + v, g = g] % mod ; else if(f == f] + v)f = f] + v, (g += g]) %= mod; zz = f < f ? j : zz; } } for(int i = 1; iq.r >> q.m, q.id = i; solve(1, n, 1, qwq); for(int i = 1; i
页:
[1]