原题链接：https://vjudge.net/problem/UVA-1354 分类：二进制法 备注：枚举二叉树,好题
根据紫书思路：每次从集合任意选两个节点组成一个新节点。
之前自己试的时候，并没有用什么技巧，但是没做出来，然后看了作者的代码，实在是妙啊。这部分之前的内容讲了子集生成，有增量构造法，位向量法，二进制法。见识了二进制法的妙用，比自己想的快多了。 以后有时间就算能自己写出例题也应该看看lrj的代码，毕竟都是精品，光顾着自己的那点可怜知识，就算写出了题也不一定有多少进步。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn = 7; struct node { double L, R; node() :L(0), R(0) {} }; int t, s, vis[1 << maxn];//标记集合是否被访问过 double r, w[maxn], sum[1 << maxn];//标记集合i的总重量 vector<node>tree[1 << maxn];//tree[i]表示集合i对应的结果 void print(int x) {//自己查看二进制数是如何运行的代码= =、 int a[7], pos = 0; while (x) { a[pos++] = x % 2; x /= 2; } for (int i = pos; i < s; i++)printf("0"); for (int i = pos - 1; i >= 0; i--) printf("%d", a[i]); printf("\n"); } void dfs(int subset) { if (vis[subset])return; vis[subset] = 1; bool hav_children = false; for (int lef = (subset - 1) & subset; lef; lef = (lef - 1) & subset) { //a&(a-1)可以去掉a的二进制数上最右边的1,作为左子树 hav_children = true; int rig = subset ^ lef;//rig为被去掉的所有的1,作为右子树 /*printf("subset::"); print(subset); printf("lef::"); print(lef); printf("rig::"); print(rig);*/ double d1 = sum[rig] / sum[subset]; double d2 = sum[lef] / sum[subset]; dfs(lef); dfs(rig);//找遍左右子树的所有可能 //任意选出一个左子树和一个右子树进行搭配 for (int i = 0; i < tree[lef].size(); i++) { for (int j = 0; j < tree[rig].size(); j++) { node t; t.L = max(tree[lef][i].L + d1, tree[rig][j].L - d2); t.R = max(tree[rig][j].R + d2, tree[lef][i].R - d1); if (t.L + t.R < r)tree[subset].push_back(t); } } } if (!hav_children)tree[subset].push_back(node());//叶子无子树,要保证父亲能利用 } int main(void) { scanf("%d", &t); while (t--) { memset(vis, 0, sizeof(vis)); scanf("%lf %d", &r, &s); for (int i = 0; i < s; i++)scanf("%lf", &w[i]); for (int i = 0; i < (1 << s); i++) { sum[i] = 0; tree[i].clear(); for (int j = 0; j < s; j++) if (i & (1 << j))sum[i] += w[j]; } int root = (1 << s) - 1; dfs(root); double ans = -1; for (int i = 0; i < tree[root].size(); i++) ans = max(ans, tree[root][i].L + tree[root][i].R); printf("%.16f\n", ans); } return 0; }自己的失败代码在此：
目前找不到错误的原因，每次考虑了左右力臂的两种情况，缺点应该就是慢了点。像上面的二进制法，C++用二进制运算符是很快的，应当加强对二进制在集合上的应用的理解。 有点可惜的就是这份代码的答案和uDebug的答案误差没超过10^-8，按理来说应该能AC的… 补：第一个5W例子的，从输出16位小数变成输出15位小数，答案完全匹配…
#include<cstdio> #include<algorithm> using namespace std; const int maxn = 6; int t, s; double r, ans; struct node { double weight, lef, rig; node(int _w = 0, double _l = 0, double _r = 0) :weight(_w), lef(_l), rig(_r) {} };//中心的位置,左边长和右边长 void dfs(node* g, int len) { for (int i = 0; i < len - 1; i++) for (int j = i + 1; j < len; j++) { double tot = g[i].weight + g[j].weight; double lef = g[j].weight / tot; double rig = g[i].weight / tot; //g[i]在左,g[j]在右 左臂+原左臂 右臂+原右臂 node nowNode(g[i].weight + g[j].weight, max(lef + g[i].lef, g[j].lef - rig), max(rig + g[j].rig, g[i].rig - lef)); node tmp[maxn]; tmp[0] = nowNode; for (int k = 1, pos = 0; k < len - 1; k++) { while (pos == i || pos == j)pos++; tmp[k] = g[pos++]; } if (nowNode.lef + nowNode.rig < r) { if (len == 2) ans = max(ans, nowNode.lef + nowNode.rig); else dfs(tmp, len - 1); } //g[j]在左,g[i]在右,此时rig是左臂,lef是右臂 tmp[0].lef = max(g[j].lef + rig, g[i].lef - lef); tmp[0].rig = max(g[i].rig + lef, g[j].rig - rig); if (tmp[0].lef + tmp[0].rig < r) { if (len == 2) ans = max(ans, tmp[0].lef + tmp[0].rig); else dfs(tmp, len - 1); }//增加 } } int main(void) { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d", &t); while (t--) { node g[maxn]; scanf("%lf %d", &r, &s); for (int i = 0; i < s; i++) { double w; scanf("%lf", &w); g[i] = node(w, 0, 0); } if (s == 1) { printf("%.15f\n", 0); continue; } ans = -1; dfs(g, s); printf("%.15f\n", ans); } return 0; }