【HDOJ】1171 Big Event in HDU

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define MAXNUM 500000
 5 
 6 typedef struct {
 7     int val, num;
 8 } fac_st;
 9 
10 fac_st facs[55];
11 int c1[MAXNUM], c2[MAXNUM];
12 
13 int main() {
14     int n, sum, tmp;
15     int i, j, k;
16 
17     while (scanf("%d", &n) != EOF && (n>=0)) {
18         sum = 0;
19         for (i=1; i<=n; ++i) {
20             scanf("%d %d", &facs[i].val, &facs[i].num);
21             sum += facs[i].val * facs[i].num;
22         }
23         memset(c1, 0, sizeof(c1));
24         memset(c2, 0, sizeof(c2));
25         for (i=0, j=0; i<=facs[1].num; ++i, j+=facs[1].val)
26             c1[j] = 1;
27         for (i=2; i<=n; ++i) {
28             for (j=0; j<=sum; ++j) {
29                 tmp = facs[i].val * facs[i].num;
30                 for (k=0; k<=tmp && (k+j)<=sum; k+=facs[i].val)
31                     c2[k+j] += c1[j];
32             }
33             for (j=0; j<=sum; ++j) {
34                 c1[j] = c2[j];
35                 c2[j] = 0;
36             }
37         }
38         k = sum/2;
39         if (c1[k])
40             printf("%d %d
", sum-k, k);
41         else {
42             for (i=k+1; i<=sum; ++i)
43                 if (c1[i]) {
44                     printf("%d %d
", i, sum-i);
45                     break;
46                 }
47         }
48     }
49 
50     return 0;
51 }