【HDOJ】2191 悼念512汶川大地震遇难同胞—

【HDOJ】2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

多重背包。

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int ps, hs, cs, dp[105];
 5 int n, m;
 6 
 7 void completePac(int p, int h) {
 8     int i, tmp;
 9 
10     for (i=p; i<=n; ++i) {
11         tmp = dp[i-p] + h;
12         if (dp[i] < tmp)
13             dp[i] = tmp;
14     }
15 }
16 
17 void onezeroPac(int p, int h) {
18     int i, tmp;
19 
20     for (i=n; i>=p; --i) {
21         tmp = dp[i-p] + h;
22         if (dp[i] < tmp)
23             dp[i] = tmp;
24     }
25 }
26 
27 void multiPac(int p, int h, int c) {
28     int k;
29 
30     if (p*c >= n) {
31         completePac(p, h);
32         return ;
33     }
34     k = 1;
35     while (k < c) {
36         onezeroPac(k*p, k*h);
37         c -= k;
38         k *= 2;
39     }
40     if (c)
41         onezeroPac(c*p, c*h);
42 }
43 
44 int main() {
45     int c;
46     int i;
47 
48     scanf("%d", &c);
49 
50     while (c--) {
51         scanf("%d %d", &n, &m);
52         memset(dp, 0, sizeof(dp));
53         for (i=0; i<m; ++i) {
54             scanf("%d %d %d", &ps, &hs, &cs);
55             multiPac(ps, hs, cs);
56         }
57         printf("%d
", dp[n]);
58     }
59 
60     return 0;
61 }