HDU 1171 Big Event in HDU

http://acm.hdu.edu.cn/showproblem.php?pid=1171

我坑在了两个地方, 首先看到-1的时候就结束, 然后就是-1了. 再是数组的范围我一直以为是 100*1000 的, 结果还是小.

这题为多重背包, 其中 V , W 的值是相同的. 是不是可以用什么单调队列优化?.....

View Code

 1 #include <iostream>
 2 #define maxn 125005
 3 using namespace std;
 4 long ans[maxn], v[maxn], num[maxn], n, m;
 5 void complete_pack(long v)
 6 {
 7     int i;
 8     for(i = 0; i <= m; i++)
 9     if(i >= v && ans[i-v]+v > ans[i])
10     ans[i] = ans[i-v]+v;
11 }
12 void zero_one_pack(long v)
13 {
14     int i;
15     for(i = m; i >= v; i--)
16     if(ans[i-v]+v > ans[i])
17     ans[i] = ans[i-v]+v;
18 }
19 void mulity_pack()
20 {
21     int i, j;
22     for(i = 0; i <=m ; i++)
23     ans[i] = 0;
24     for(i = 0; i < n; i++)
25     {
26         if(v[i]*num[i] >= m)
27         {
28             complete_pack(v[i]);
29         }
30         else
31         {
32             for(j = 1; j < num[i]; )
33             {
34                 zero_one_pack(j*v[i]);
35                 num[i] -= j;
36                 j *= 2;
37             }
38             zero_one_pack(num[i]*v[i]);
39         }
40     }
41 }
42 int main()
43 {
44     long i, sum;
45     while(cin >> n)
46     {
47         if(n<0) break;
48         sum = 0;
49         for(i = 0; i < n; i++)
50         {
51             cin >> v[i] >> num[i];
52             sum += v[i] * num[i];
53         }
54         m = sum/2;
55         mulity_pack();
56         cout << sum -ans[m] << " " << ans[m] << endl;
57     }
58     return 0;
59 }