传送门1(UVa): https://uva.onlinejudge.org/external/13/1354.pdf
传送门2(GOJ): http://acm.gdufe.edu.cn/Problem/read/id/1320
题意： 长度限制 r (1 < r < 10)， 给 n (1 <= n <= 6) 个砝码，组成平衡(考虑重量和力臂)的天平，求天平最长能多长。
2015个人选拔赛#6 1004
比赛的时候完全不知道怎么做，比赛完两天重新看一遍有点思路就是敲不出来(弱渣...)=_=
跟着Wenjun师兄的代码学了一下
caodan的是最近在写多重for循环的时候总是在里层写错变量........找半天啊还好几个啊我这是怎么了................
二进制枚举，类似线段树从底层一层一层处理
#include <bits/stdc++.h> using namespace std; struct Tree{ double l, r; Tree(double ll = 0.0, double rr = 0.0): l(ll), r(rr) {} }; const int MAXN = 6; int n; bool vis[1<<MAXN]; // 是否访问过该子集 double r, w[MAXN], sum[1<<MAXN]; vector<Tree> tree[1<<MAXN]; // 保存各子集符合题意的解 // 计算该子集包含的砝码个数，当为1时相当于到达二叉树结点 int count(int x){ int ans = 0; for(int i = 0; i < n; ++i) if(x & (1<<i)) ++ans; return ans; } void dfs(int subset){ if(vis[subset]) return ; vis[subset] = true; if(count(subset) == 1){ tree[subset].push_back(Tree()); return; } //枚举该集合的所有子集 for(int left = (subset-1) & subset; left; left = (left-1) & subset){ int right = subset ^ left; //根据公式求当前左右集合对应力臂长度 double leftlen = sum[right] / sum[subset]; double rightlen = 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){ double ll = max(tree[left][i].l + leftlen, tree[right][j].l - rightlen); double rr = max(tree[right][j].r + rightlen, tree[left][i].r - leftlen); if(ll + rr < r) tree[subset].push_back(Tree(ll, rr)); } } } } 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]); for(int i = 0; i < (1<<n); ++i){ sum[i] = 0; tree[i].clear(); for(int j = 0; j < n; ++j){ if((i>>j) & 1) sum[i] += w[j]; //二进制枚举各个子集的重量和 } } int root = (1<<n) - 1; //整个天平 memset(vis, false, sizeof(vis)); 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); if(ans == -1) printf("-1 "); else printf("%.15lf ", ans); } return 0; }