NC20058. [HNOI2007]梦幻岛宝珠
描述
输入描述
输入文件中包含多组数据。每组数据的格式如下：
第一行是两个正整数n和W，1 ≤ n ≤ 100,1 ≤ W ≤ 2^30，分别表示宝石的数目和最多能带走的宝石重量。
接下来的n行，每行有两个正整数weighti和valuei，1 ≤ weighti ≤ 2^30, 0 ≤ valuei ≤ 2^30，分别表示第i颗宝石的重量和价值，且保证weighti能写成a*2^b(1 ≤ a ≤ 10,0 ≤ b ≤ 30)的形式。
同一行的两个正整数之间用空格隔开。最后一组数据的后面有两个-1，表示文件的结束。这两个-1并不代表一组数据，你不需对这组数据输出结果。并且输入文件中数据的组数不超过20。
输出描述
对于输入的每组数据，输出一个整数C，表示小P最多能带走的宝石的总价值。每个结果整数C单独占一行，且保证C不会超过2^30。
示例1
输入:
4 10 8 9 5 8 4 6 2 5 4 13 8 9 5 8 4 6 2 5 16 75594681 393216 5533 2 77 32768 467 29360128 407840 112 68 24576 372 768 60 33554432 466099 16384 318 33554432 466090 2048 111 24576 350 9216 216 12582912 174768 16384 295 1024 76 -1 -1
输出:
14 19 1050650
C++ 解法, 执行用时: 327ms, 内存消耗: 652K, 提交时间: 2021-10-20 13:29:13
#include <cstdio>
#include <cstring>
#include <algorithm>
#define UPD(x,y) x=std::max(x,y)
#define Min(x,y) std::min(x,y)
int n,w,f[35][1005];
int main() {
while(scanf("%d%d",&n,&w)==2&&((~n)||(~n))) {
memset(f,0,sizeof(f));
for(int i=0;i<n;++i) {
int a,b=0,v;
scanf("%d%d",&a,&v);
while(!(a&1)) {++b;a>>=1;}
for(int j=1000;j>=a;--j) UPD(f[b][j],f[b][j-a]+v);
}
int top=-1;for(int i=w;i;i>>=1) ++top;
for(int i=1;i<=top;++i) {
for(int j=1000;j>=0;--j) for(int k=0;k<=j;++k)
UPD(f[i][j],f[i][j-k]+f[i-1][Min(1000,(k<<1)|(w>>(i-1)&1))]);
}
printf("%d\n",f[top][1]);
}
return 0;
}