梦幻岛宝珠

题目链接：https://ac.nowcoder.com/acm/problem/20058
题解如下：
这波01背包的容量有点大，直接0/1背包打上去肯定是 MLE+TLE。
我们注意到，数据保证物品质量都是2的整次幂的较小倍数, so我们可以把所有物品按照最接近的2的整次幂分组, 分别做0/1背包之后, 由于各组物品质量数量级相差较大, 最后只要直接把同一组的结果当成一个，然后乱搞就好了。

这道题难度的话还好吧。。。容量有点大啊
硬解原地爆炸
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
const int MAXN=1e3+10;
int n,w;
LL ans=0;
LL dp[40][MAXN];</algorithm></iostream></cstdlib></cstring></cstdio>

void FR(int&);

int main(){
FR(n);
FR(w);
while(n>=0&&w>=0){
memset(dp,0,sizeof(dp));
ans=0;
for(int i=1;i<=n;i++){
int val,cnt=0,wgh;
FR(wgh);
FR(val);
while((wgh&1)==0){
wgh>>=1;
cnt++;
}
for(int j=1000;j>=wgh;j--){
dp[cnt][j]=std::max(dp[cnt][j],dp[cnt][j-wgh]+val);
}
}
for(int i=0;i<=30;i++){
for(int j=1;j<=1000;j++){
dp[i][j]=std::max(dp[i][j],dp[i][j-1]);
}
}
for(int i=1;i<=std::min(1000,w);i++){
ans=std::max(ans,dp[0][i]);
}
for(int i=1;i<=30&&(1<<i)<=w;i++){
for(int j=std::min(1000,w>>i);j>=0;j--){
for(int k=0;k<=j;k++)
dp[i][j]=std::max(dp[i][j],dp[i][j-k]+dp[i-1][std::min(k*2+((w>>(i-1)&1)),1000)]);
ans=std::max(ans,dp[i][j]);
}
}
printf("%lld\n",ans);
FR(n);
FR(w);
}
return 0;
}

void FR(int& opc){
opc=0;
bool inv=false;
register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')
inv=true;
ch=getchar();
}
while(isdigit(ch)){
opc=opc*10+ch-'0';
ch=getchar();
}
if(inv)
opc=-opc;
}