【POJ 2923】Relocation

Description

Emma and Eric are moving to their new house they bought after returning from their honeymoon. Fortunately, they have a few friends helping them relocate. To move the furniture, they only have two compact cars, which complicates everything a bit. Since the furniture does not fit into the cars, Eric wants to put them on top of the cars. However, both cars only support a certain weight on their roof, so they will have to do several trips to transport everything. The schedule for the move is planed like this:

  1. At their old place, they will put furniture on both cars.
  2. Then, they will drive to their new place with the two cars and carry the furniture upstairs.
  3. Finally, everybody will return to their old place and the process continues until everything is moved to the new place.

Note, that the group is always staying together so that they can have more fun and nobody feels lonely. Since the distance between the houses is quite large, Eric wants to make as few trips as possible.

Given the weights wi of each individual piece of furniture and the capacities C1 and C2 of the two cars, how many trips to the new house does the party have to make to move all the furniture? If a car has capacity C, the sum of the weights of all the furniture it loads for one trip can be at most C.

Input

The first line contains the number of scenarios. Each scenario consists of one line containing three numbers nC1 and C2C1 and C2 are the capacities of the cars (1 ≤ Ci ≤ 100) and n is the number of pieces of furniture (1 ≤ n ≤ 10). The following line will contain n integers w1, …, wn, the weights of the furniture (1 ≤ wi ≤ 100). It is guaranteed that each piece of furniture can be loaded by at least one of the two cars.

Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line with the number of trips to the new house they have to make to move all the furniture. Terminate each scenario with a blank line.

Sample Input

2
6 12 13
3 9 13 3 10 11
7 1 100
1 2 33 50 50 67 98

Sample Output

Scenario #1:
2

Scenario #2:
3

大意:

要搬运N个货物,每个货物有一定的重量,现在有2辆车,每辆车有一定的容量C1、C2,要求每辆车装载的货物重量之和不超过车的容量,两辆车一起搬运,求出最少的搬运次数。(N <= 10,C <= 100)

分析:

首先可以注意到货物的个数很少,只有10,那么可以考虑用状态压缩。

将每一次搬运的方案(用0、1表示某个货物是否被选择)压缩成一个 sta,用数组存下所有可行的方案。

判断一个方案可不可行,先用sum记下所有选中的货物的重量和,判断可以用背包来做,f[i]可以表示当背包容量为i时,在这个方案中可以装下的最大的质量,做完背包然后枚举i为1~C1,判断如果C2 >= sum - f[i],那么则该方案可行。

找出所有可行方案后,再用背包来将状态000……000转移到111……111,转移方程如下:

DP[i | sta[j]] = min (DP[i | sta[j]], DP[i] + 1)

其中i为当前的状态(即当前哪些货物已经被搬运),j是枚举所有可行的状态,i | sta[j]表示搬运了这些货物后的状态,每次转移的代价为1,最后输出DP[(1 << N) - 1](即111……111)。

题目不保证C1 < C2,特殊判断一下使C1 < C2 可以提高效率。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 int t, n, c1, c2, w[11], sta[1 << 11], cnt, dp[1 << 11];
 4 inline int max (int a, int b)
 5 {
 6     return a > b ? a : b;
 7 }
 8 inline int min (int a, int b)
 9 {
10     return a < b ? a : b;
11 }
12 bool check (int s)
13 {
14     int f[110], sum = 0;
15     memset (f, 0, sizeof (f));
16     for (int i = 0; i < n; i++)
17     {
18         if (s & (1 << i))
19         {
20             sum += w[i];
21             for (int j = c1; j >= w[i]; j--)
22                 f[j] = max (f[j], f[j - w[i]] + w[i]);
23         }
24     }
25     for (int i = 0; i <= c1; i++)
26         if (c2 >= sum - f[i]) return 1;
27     return 0;
28 }
29 int main ()
30 {
31     scanf ("%d", &t);
32     for (int p = 1; p <= t; p++)
33     {
34         scanf ("%d %d %d", &n, &c1, &c2);
35         c1 > c2 ? c1 ^= (c2 ^= (c1 ^= c2)) : 0; //swap
36         for (int i = 0; i < n; i++)
37             scanf ("%d", &w[i]);
38         memset (dp, 63, sizeof (dp)); dp[0] = cnt = 0;
39         for (int i = 0; i < (1 << n); i++)
40             if (check (i)) sta[cnt++] = i;
41         for (int i = 0; i < (1 << n); i++)
42             for (int j = 0; j < cnt; j++)
43                 dp[i | sta[j]] = min (dp[i | sta[j]], dp[i] + 1);
44         printf("Scenario #%d:\n%d\n\n", p, dp[(1 << n) - 1]);
45     }
46     return 0;
47 }
时间: 02-27

【POJ 2923】Relocation的相关文章

【POJ 1408】 Fishnet (叉积求面积)

[POJ 1408] Fishnet (叉积求面积) 一个1*1㎡的池塘 有2*n条线代表渔网 问这些网中围出来的最大面积 一个有效面积是相邻两行和相邻两列中间夹的四边形 Input为n 后面跟着四行 每行n个浮点数 每一行分别代表a,b,c,d 如图 并且保证a(i) > a(i-1) b(i) > b(i-1) c(i) > c(i-1) d(i) > d(i-1) n(n <= 30)*2+4(四个岸)条边 枚举点数就行 相邻的四个四个点枚举 找出围出的最大面积 找点用

【POJ 2513】Colored Sticks

[POJ 2513]Colored Sticks 并查集+字典树+欧拉通路 第一次做这么混的题..太混了-- 不过题不算难 字典树用来查字符串对应图中的点 每个单词做一个点(包括重复单词 题意就是每个边走且直走一次(欧拉通路 欧拉图的判定: 没有或者只有两个奇数度的点的图叫做欧拉图 有这些就可以解答此题了 另外需要注意题目范围是25W个木棍 所以最多可能有50W个点 卡了好多个RE 代码如下: #include <iostream> #include <cstdlib> #incl

2292: 【POJ Challenge 】永远挑战

2292: [POJ Challenge ]永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 553  Solved: 230[Submit][Status][Discuss] Description lqp18_31和1tthinking经常出题来虐ftiasch.有一天, lqp18_31搞了一个有向图,每条边的长度都是1. 他想让ftiasch求出点1到点 N 的最短路."水题啊.", ftiasch这么说道. 所以1tth

【POJ 1201】 Intervals(差分约束系统)

[POJ 1201] Intervals(差分约束系统) 11 1716的升级版 把原本固定的边权改为不固定. Intervals Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 23817   Accepted: 9023 Description You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. Write a p

【POJ 1228】Grandpa&#39;s Estate 凸包

找到凸包后暴力枚举边进行$check$,注意凸包是一条线(或者说两条线)的情况要输出$NO$ #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define N 1003 #define read(x) x = getint() using namespace std; inline int getint() { int k = 0, fh = 1; char c

【POJ 2750】 Potted Flower(线段树套dp)

[POJ 2750] Potted Flower(线段树套dp) Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 4566   Accepted: 1739 Description The little cat takes over the management of a new park. There is a large circular statue in the center of the park, surrou

【POJ 2480】Longge&#39;s problem(欧拉函数)

题意 求$ \sum_{i=1}^n gcd(i,n) $ 给定 $n(1\le n\le 2^{32}) $. 链接 分析 用欧拉函数$φ(x)$求1到x-1有几个和x互质的数. gcd(i,n)必定是n的一个约数.若p是n的约数,那么gcd(i,n)==p的有$φ(n/p)$个数,因为要使gcd(i,n)==p,i/p和n/p必须是互质的.那么就是求i/p和n/p互质的i在[1,n]里有几个,就等价于,1/p,2/p,...,n/p里面有几个和n/p互质,即φ(n/p). 求和的话,约数为p

【POJ 3321】 Apple Tree (dfs重标号设区间+树状数组求和)

[POJ 3321] Apple Tree (dfs重标号设区间+树状数组求和) Apple Tree Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 21966   Accepted: 6654 Description There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. K

【POJ 1260】Pearls

[POJ 1260]Pearls dp问题 最近做背包做多了 一做动规就往背包想-- 这题其实也有点背包的意思(然而只是做背包做的看啥都像背包-- c件物品 有各自的数量a 和价值p 每进行一次交易的花费cost = (物品数+10)*价格 低价物品可以用高价一起购买 一次交易只能按照一种价值购买 初始dp[0] = 0 dp数组下标为物品件数 枚举物品种类 没枚举一种物品 遍历该物品之前物品量 假设之前有num件物品 当前枚举到的物品价值p 那么就要找到min(dp[k(0~num)] + (