P1776 宝物筛选_NOI导刊2010提高（02）&& 多重背包二进制优化

多重背包， 要求 (Nlog N) 复杂度

Solution

众所周和， (1-N) 之内的任何数可以由 (2^{0}, 2^{1}, 2^{2} ... 2^{log N}, N - 2^{log N}) 拼凑而成
我们知道一定有一种最优方案， 使得第 (i) 种物品只消耗 (x) 个 ((x <= n_{i}))
而 (x) 可以被二进制凑出来
所以我们先二进制拆分物品件数， 再跑 (01) 背包即可

P1776 宝物筛选_NOI导刊2010提高（02）

板题

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
#define LL long long
using namespace std;
LL RD(){
    LL out = 0,flag = 1;char c = getchar();
    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
    return flag * out;
    }
const LL maxn = 2000019;
LL num, V;
LL v[maxn], w[maxn], cnt;
LL dp[maxn];
int main(){
	num = RD(), V = RD();
	for(LL i = 1;i <= num;i++){
		LL val = RD(), wei = RD(), n = RD(), t = 1;
		while(n >= t){
			v[++cnt] = val * t, w[cnt] = wei * t;
			n -= t;
			t <<= 1;
			}
		v[++cnt] = val * n, w[cnt] = wei * n;
		}
	for(LL i = 1;i <= cnt;i++){
		for(LL j = V;j >= w[i];j--){
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
	printf("%lld
", dp[V]);
	return 0;
	}