【ZOJ月赛】【存在性背包问题】【G.E Cup 3】

【题目来源】http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4935

【个人体会】后来发现我的代码质量竟然排在第一位，真心有点吃惊。。。

【题目解析】建立一个容量为min(S1,S2)的背包，将每个房间的容量看成是一个个物品，将物品放入背包中，F[i]表示的是容量为i的背包的路径数。对于容量为奇数的房间，直接按01背包做，对于容量为偶数的房间，按分组背包做，每组有3个背包(0,1,0.5)。

【代码如下】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int mod = 1000000007;
 8 int S1, S2, N, V, A[201], F[100001];
 9 
10 void Clear()
11 {
12     memset(F, 0, sizeof(F));
13 }
14 
15 void Dp()
16 {
17     F[0] = 1; V = min(S1, S2);
18     for (int i = 1; i <= N; ++i)
19         for (int j = V - A[i] / 2; j >= 0; j --)
20             if (F[j])
21             {
22                 if (j + A[i] <= V) F[j + A[i]] = (F[j] + F[j + A[i]]) % mod;
23                 if (A[i] & 1) continue;
24                 int tmp = A[i] / 2;
25                 F[j + tmp] = (F[j] + F[j + tmp]) % mod;
26             }
27     printf("%d\n", F[V]);
28 }
29 
30 void Init()
31 {
32     scanf("%d", &N);
33     for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
34 }
35 
36 int main()
37 {
38     while (scanf("%d%d", &S1, &S2) != EOF)
39     {
40         Init();
41         Dp();
42         Clear();
43     }
44     return 0;
45 }