UVa 1354 天平难题

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4100

题意:给出房间的宽度和挂坠的重量，设计一个尽量宽的天平，挂着所有挂坠，当然不可以超过房间宽度。

这道题我真的是一点想法都没有，也不知道怎么去枚举二叉树好，下面都是参考别人的代码，我自己也思考了很久，总算是搞清楚了，用二进制法来枚举子集，太妙了。

这样一来也就可以不用特别考虑右子树的左子树比左子树的左子树长的情况了。

 1 #include<iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 1 << 6;
 9 int s;
10 double r;
11 int vis[maxn];
12 double sum[maxn];
13 double w[10];
14 
15 struct Node
16 {
17     double l, r;
18     Node(double x, double y) { l = x; r = y; }
19     Node() {}
20 };
21 
22 vector<Node> node[maxn];
23 
24 int bitcount(int x)
25 {
26     if (x == 0)    return 0;
27     return bitcount(x / 2) + (x & 1);
28 }
29 
30 void dfs(int k)
31 {
32     if (vis[k])    return;    //如果该状态已访问，则直接返回
33     vis[k] = 1;
34     if (bitcount(k) == 1)   //如果此时只有一个1，则只有一个子集，说明是叶子节点，天平左右都为0
35     {
36         node[k].push_back(Node(0, 0));
37         return;
38     }
39     for (int l = (k - 1)&k; l > 0; l = (l - 1)&k)   //二进制法枚举左右子集
40     {
41         int r = k^l;   //求出补集，即右子集
42         dfs(l);  //继续枚举左子集
43         dfs(r);  //继续枚举右子集
44         for (int i = 0; i < node[l].size(); i++)
45         {
46             for (int j = 0; j < node[r].size(); j++)
47             {
48                 double ll = min(-sum[r] / (sum[l] + sum[r]) + node[l][i].l, sum[l] / (sum[l] + sum[r]) + node[r][j].l);
49                 double rr = max(sum[l] / (sum[l] + sum[r]) + node[r][j].r, -sum[r] / (sum[l] + sum[r]) + node[l][i].r);
50                 node[k].push_back(Node(ll, rr));   //将该节点左右臂长加入数组
51             }
52         }
53     }
54 }
55 
56 void solve()
57 {
58     double width = -1;
59     int k = (1 << s) - 1;
60     dfs(k);
61     for (int i = 0; i < node[k].size();i++)
62     if (node[k][i].r - node[k][i].l<r && node[k][i].r - node[k][i].l>width)
63         width = node[k][i].r - node[k][i].l;
64     if (width == -1)  cout << "-1" << endl;
65     else printf("%.16lf
", width);
66 }
67 
68 
69 int main()
70 {
71     int n;
72     cin >> n;
73     while (n--)
74     {
75         memset(vis, 0, sizeof(vis));
76         memset(sum, 0, sizeof(sum));
77         memset(node, 0, sizeof(node));
78         cin >> r >> s;
79         for (int i = 0; i < s; i++)
80         {
81             cin >> w[i];
82         }
83         for (int i = 0; i < (1 << s); i++)   //计算出每个子集的总重量
84         {
85             for (int j = 0; j < s; j++)
86             {
87                 if (i & (1 << j))
88                     sum[i] += w[j];
89             }
90         }
91         solve();
92     }
93     return 0;
94 }