【HDOJ】1059 Dividing

多重背包。
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define mymax(a, b) (a>b) ? a:b
 5 
 6 int c[7];
 7 int dp[60000];
 8 
 9 void ZeroOnePack(int c, int v) {
10     int i;
11 
12     for (i=v; i>=c; --i)
13         dp[i] = mymax(dp[i], dp[i-c]);
14 }
15 
16 void CompletePack(int c, int v) {
17     int i;
18 
19     for (i=c; i<=v; ++i)
20         dp[i] = mymax(dp[i], dp[i-c]);
21 }
22 
23 void MultiPack(int c, int n, int v) {
24     int k = 1;
25     if (c*n >= v) {
26         CompletePack(c, v);
27         return ;
28     }
29     while (k < n) {
30         ZeroOnePack(k*c, v);
31         n -= k;
32         k *= 2;
33     }
34     ZeroOnePack(n*c, v);
35 }
36 
37 int main() {
38     int t = 0, total;
39     int i;
40 
41     while ( 1 ) {
42         total = 0;
43         for (i=1; i<=6; ++i) {
44             scanf("%d", &c[i]);
45             total += c[i]*i;
46         }
47         if (total == 0)
48             break;
49         printf("Collection #%d:
", ++t);
50         if (total & 1) {
51             printf("Can't be divided.

");
52             continue;
53         }
54         total >>= 1;
55         memset(dp, 0, sizeof(dp));
56         dp[0] = 1;
57         for (i=1; i<=6; ++i) {
58             MultiPack(i, c[i], total);
59             if (dp[total])
60                 break;
61         }
62         if (dp[total])
63             printf("Can be divided.

");
64         else
65             printf("Can't be divided.

");
66     }
67 
68     return 0;
69 }