bzoj 1190

思路：分层dp，因为给的w都是a*(2 ^ b)的形式，我们将这些物品按b分层，我们设 dp[ i ][ j ]表示在第 i 层容量为(j << i)的最大值，

然后通过层与层之间dp 把dp[ i ][ j ] 扩充为容量为(j << i) + W & ((1 << i - 1) - 1) 的最大值，就能得出答案啦。

层和层之间的转移方程为：

dp[i][j] = max(dp[i][j], dp[i][k] + dp[i - 1][min(((j - k) << 1) + ((W >> (i - 1)) & 1), 1000)]);

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define fi first
 4 #define se second
 5 #define mk make_pair
 6 #define pii pair<int,int>
 7 #define piii pair<int, pair<int,int>>
 8 
 9 using namespace std;
10 
11 const int N=100+7;
12 const int M=1e4+7;
13 const int inf=0x3f3f3f3f;
14 const LL INF=0x3f3f3f3f3f3f3f3f;
15 const int mod=1e9 + 7;
16 
17 int n, W, two[N], ans, dp[31][1001];
18 struct node {
19     node(int w, int v) {
20         this -> w = w;
21         this -> v = v;
22     }
23     int w, v;
24 };
25 
26 vector<node> v[31];
27 
28 void init() {
29     ans = 0;
30     memset(dp, 0, sizeof(dp));
31     for(int i = 0; i <= 30; i++)
32         v[i].clear();
33 }
34 
35 int main() {
36     two[0] = 1;
37     for(int i = 1; i <= 30; i++)
38         two[i] = two[i - 1] * 2;
39 
40     while(scanf("%d%d", &n, &W) != EOF && n != -1) {
41         init();
42         for(int i = 1; i <= n; i++) {
43             int w, val;
44             scanf("%d%d", &w, &val);
45             for(int i = 30; i >= 0; i--) {
46                 if(w % two[i] == 0) {
47                     v[i].push_back(node(w / two[i], val));
48                     break;
49                 }
50             }
51         }
52 
53         for(int i = 0; i <= 30; i++) {
54             for(int u = 0; u < v[i].size(); u++) {
55                 node k = v[i][u];
56                 for(int j = min(1000, W >> i); j >= k.w; j--) {
57                     dp[i][j] = max(dp[i][j], dp[i][j - k.w] + k.v);
58                     ans = max(ans, dp[i][j]);
59                 }
60             }
61         }
62 
63 
64         for(int i = 1; i <= 30 && (1 << i) < W; i++) {
65             for(int j = min(1000, W >> i); j >= 0; j--) {
66                 for(int k = j; k >= 0; k--) {
67                     dp[i][j] = max(dp[i][j], dp[i][k] + dp[i - 1][min(((j - k) << 1) + ((W >> (i - 1)) & 1), 1000)]);
68                     ans = max(ans, dp[i][j]);
69                 }
70             }
71         }
72         printf("%d
", ans);
73     }
74     return 0;
75 }
76 /*
77 */