盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 技巧
  5. 代码
  6. 更新日志

UVa 1354 天平难题 (搜索)

题目

源地址:http://acm.bnu.edu.cn/v3/problem_show.php?pid=36971

题意

给出房间的宽度$r$和$s$个挂坠的重量$w_i$。设计一个尽量宽(但宽度不能超过房间宽度$r$)的天平,挂着所有挂坠。
天平由一些长度为1的木棍组成。木棍的每一端要么挂着一个挂坠,要么挂着另外一个木棍。
挂坠的宽度忽略不计,且不同的子天平可以相互重叠。
数据范围:$(0<r<10, 1{\leq}s{\leq}6, 1{\leq}w_i{\leq}1000)$

思路

把挂坠和木棍都作为结点,则一个天平对应一棵二叉树,可以容易的算出对应的宽度。
本题的核心任务就是枚举二叉树,采用回溯法即可。
枚举的方式是自顶向下构造,每次枚举左子树用到哪个子集,则右子树就是剩下的子集。

技巧

1
2
3
4
int subset = (1 << n) - 1; //全集
for (int left = (subset - 1) & subset; left; left = (left - 1) & subset) {
int right = subset ^ left; //leftright便是两个对应的子集
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct node {
double L, R;
node() : L(0), R(0) {}
};
const int N = 6;
int vis[1 << N], n;
double w[N], sum[1 << N], r;
vector<node> tree[1 << N];
void dfs(int subset) {
if (vis[subset]) return ;
vis[subset] = true;
bool have_child = false;
for (int left = (subset - 1) & subset; left; left = (left - 1) & subset) {
have_child = true;
int right = subset ^ left;
double d1 = sum[right] / sum[subset];
double d2 = sum[left] / sum[subset];
dfs(left); dfs(right);
for (int i = 0; i < tree[left].size(); i++) {
for (int j = 0; j < tree[right].size(); j++) {
node t;
t.L = max(tree[left][i].L + d1, tree[right][j].L - d2);
t.R = max(tree[right][j].R + d2, tree[left][i].R - d1);
if (t.L + t.R < r) tree[subset].push_back(t);
}
}
}
if (!have_child) tree[subset].push_back(node());
}
int main () {
int T;
scanf("%d", &T);
while(T--) {
scanf("%lf%d", &r, &n);
for (int i = 0; i < n; i++) scanf("%lf", w + i);
int tot = 1 << n;
for (int i = 0; i < tot; i++) {
sum[i] = 0;
tree[i].clear();
for (int j = 0; j < n; j++)
if (i & (1 << j)) sum[i] += w[j];
}
tot--;
memset(vis, 0, sizeof(vis));
dfs(tot);
double ans = -1;
for (int i = 0; i < tree[tot].size(); i++)
ans = max(ans, tree[tot][i].L + tree[tot][i].R);
printf("%.10lf\n", ans);
}
return 0;
}

更新日志

  • 29 ms 1712 B 2014-10-28 17:51:13