bzoj1190,懒得复制,戳我戳我
Solution:
- 这道题其实是一个背包(分组背包),但是由于数字比较大,就要重新构造dp式子。啃了三天才懂。
-
\(dp[i][j]\)表示背包容积为\(j*2^i\)时的最大价值。
- 首先,因为每一个物品一定是\(a*2^b\),我们可以按照\(b\)值先按照普通的分组背包去做,处理出每个\(b\)值所对应的\(dp\)值
- 然后我们就是要把这些\(dp\)值累积起来,选择每组最大显然不合适,因为有可能每个组都剩下空间,剩余空间累加起来的空间还可以放物品,我们采用一下\(dp\)方法:
\[dp[i][j] = max(dp[i][j] , dp[i][j-k]+dp[i-1][2*k+(w>>(i-1))])\]
-
\(i\)表示次方,\(j\)表示系数,\(k\)表示让出多少位置给\(i-1\)次方
- 我们次方从小(\(1\))枚举到大(\(W\)最高位),系数从大枚举到小,要保证\(i\)位上的最大价值是没有更新过得,也就是不包括前面位置(\(2^{i-1}\))的物品,然后加上上一层(\(i-1\))最大放的空间的\(dp\)值(因为空间最大,所以存的价值一定是最大的)
- 另外还有一个小细节,我们要把前面预处理每组背包时处理到\(2\)倍,因为后面更新时,会把\(i\)层腾的空间传给\(i-1\)层,例如\(i\)层腾了\(k\)空间,也就是\(i-1\)层多有\(2*k\)的空间,再加上\(W\)里面\(i-1\)位的空间就是\(i-1\)的空间最大
- 最后输出\(dp[cnt][1]\),\(cnt\)是最高位,因为是最高位,所以最高位上一定是\(1\)
- 看得还是比较迷糊的,戳这里,这个博客讲的挺详细的
- 好像\(HNOI2007\)的题目都好毒瘤23333……
Code:
//It is coded by Ning_Mew on 4.19
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=107;
int n,cnt=0;
LL W,dp[maxn][2005],v,w;
int main(){
while(1){
memset(dp,0,sizeof(dp));
scanf("%d%lld",&n,&W);
if(n==-1)break;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&w,&v);
cnt=0;
while(w%2==0)cnt++,w=w/2;
//cout<<"w:"<<cnt<<' '<<w<<endl;
for(int i=2000;i>=w;i--){
dp[cnt][i]=max(dp[cnt][i],dp[cnt][i-w]+v);
}
}
cnt=0;
for(int i=30;i>=0;i--)if((W>>i)&1){cnt=i;break;}
//cout<<"w:"<<cnt<<' '<<W<<endl;
for(int i=1;i<=cnt;i++){
for(int j=1000;j>=0;j--){
for(int k=0;k<=j;k++){
dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[i-1][2*k+((W>>(i-1))&1)]);
}
}
}
printf("%lld\n",dp[cnt][1]);
}
return 0;
}