# 【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


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

 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 }

## 【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 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 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)] + (