梦幻岛宝珠题解

圆题链接

01背包冲鸭！！！

好吧他死了，考虑每一个物品体积都为(b*2^a)尝试进制优化
首先设背包大小为(m)
设(f_{i,j})为背包大小最高位为(j*2^i)时最大价值
也就是说，设现在考虑的物品编号为(k)，则背包大小为(j*2^i)+(()(w_k)&(((1<<i)-1))))
原来我们是枚举整个背包大小，而现在我们不再考虑低于第(i)位的确切数值
比如当(w_k=1001)，(i=5,j=1)，背包大小为(11001)（除了(i)，以上均为二进制）
转移则为(f_{i,j}=max(f_{i,j},f_{i,j-d}+f{i-1,2*d|((m>>(i-1))-1)}))
就是说考虑从(i-1)处转移过来(2^i*d)大小的体积，由于(i)减了(1)，(d)相应要乘(2)
就是(f_{i-1,2*d})，考虑背包自身上限，还可以加上一个(2*d+((m>>(i-1))-1)

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll N=1005;
ll n,m,f[35][N],a[N],b[N],top;

int main(){
	scanf("%lld%lld",&n,&m);
	while(n!=-1&&m!=-1){
		top=0;
		memset(f,0,sizeof f);
		for(ll i=1;i<=n;i++){
			ll cnt=0,x;
			scanf("%lld%lld",&a[i],&b[i]),x=a[i];
			while(x%2==0){x/=2,cnt++;}
			for(ll j=1000;j>=x;j--){
				f[cnt][j]=max(f[cnt][j],f[cnt][j-x]+b[i]);
			}
		}
		for(ll i=m;i>0;i/=2)top++;
		top--;
		for(ll i=1;i<=top;i++){
			for(ll j=1000;j>=0;j--){
				for(ll k=0;k<=j;k++){
					f[i][j]=max(f[i][j],f[i][j-k]+f[i-1][min(1000*1ll,(k*2)|((m>>(i-1))&1))]);
				}
			}
		} 
		printf("%lld
",f[top][1]);
		scanf("%lld%lld",&n,&m); 
	}
}

代码比较憨，请见谅