poj 2923 Relocation 解题报告

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int INF = 1e9;
 8 const int maxn = 100 + 5;
 9 int w[maxn];
10 int c1, c2, cnt, n;
11 int dp[1<<10], state[1<<10];   
12 // dp[i]：状态为i时需要的最少趟数
13 // state[i]：两辆车一趟可以运的合理状态
14 
15 void dfs(int num, int c1, int c2, int s)  // s：每一次决策完的状态
16 {
17     if (num >= n)  // n件物品全部决策完
18     {
19         if (!dp[s])  // 这个状态之前没试过
20         {
21             dp[s] = 1;
22             state[cnt++] = s;  
23         }
24         return;
25     }
26     if (c1 >= w[num])
27         dfs(num+1, c1-w[num], c2, s|(1<<num));  // 尝试装去第一部车上   
28     if (c2 >= w[num])
29         dfs(num+1, c1, c2-w[num], s|(1<<num));  // 尝试装去第二部车上
30     dfs(num+1, c1, c2, s);  // 两车都不装
31 }
32 
33 int main()
34 {
35     int T, cas = 0;
36     while (scanf("%d", &T) != EOF)
37     {
38         while (T--)
39         {
40             scanf("%d%d%d", &n, &c1, &c2);
41             for (int i = 0; i < n; i++)
42                 scanf("%d", &w[i]);
43             memset(dp, 0, sizeof(dp));
44             cnt = 0;
45             dfs(0, c1, c2, 0);
46             for (int i = 0; i <= (1<<n)-1; i++)
47                 dp[i] = (i == 0 ? 0 : INF);
48     //        memset(dp, 0x3f, sizeof(dp));
49     //        dp[0] = 0;
50     //        printf("cnt = %d\n", cnt);
51             for (int i = 0; i < (1<<n); i++)  // 枚举状态数
52             {
53                 for (int j = 0; j < cnt; j++)
54                 {
55                     if (i & state[j])   // 同一件物品被选了两次，有冲突（真厉害的操作啊~）
56                         continue;
57                     int newstate = i | state[j];  // 新的一个状态
58                     dp[newstate] = min(dp[newstate], dp[i]+1);
59                 }
60             }
61             printf("Scenario #%d:\n%d\n", ++cas, dp[(1<<n)-1]);
62             if (T)
63                 puts("");
64         }
65     }
66     return 0;
67 }