题目：Mobile Computing
题意：有s块石头，用一些长为1的木棍挂着，满足杠杆平衡条件。问在房间里最宽能挂下多宽。
思路：
这种方法不会做，看了书上代码。
从上向下枚举二叉树。
详见刘汝佳代码的注释。
思路2：uva 1354 Mobile Computing
代码：
我的：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
using namespace std;#define N 6struct Pair {double x,y;Pair() {}Pair(double one,double two) {x=one,y=two;}
};int n;
double Droom;
int w[N]= {0};
int sum[1<<N];
bool use[1<<N];
vector<Pair> tree[1<<N];void init(){memset(sum,0,sizeof(sum));memset(use,0,sizeof(use));for(int i=0;i<(1<<N);i++) tree[i].clear();
}void dfs(int root) {if(use[root]) return ;use[root]=true;bool c=false;for(int left=(root-1)&root; left!=0; left=(left-1)&root) {c=true;int right=left^root;dfs(left),dfs(right);double dl=(double)sum[right]/sum[root];double dr=(double)sum[left]/sum[root];for(int i=0; i<tree[left].size(); i++) {for(int j=0; j<tree[right].size(); j++) {double L=max(tree[left][i].x+dl,tree[right][j].x-dr);double R=max(tree[left][i].y-dl,tree[right][j].y+dr);if(L+R<=Droom) tree[root].push_back(Pair(L,R));}}}if(!c) tree[root].push_back(Pair(0,0));
}int main() {int T;scanf("%d",&T);while(T--) {init();scanf("%lf%d",&Droom,&n);for(int i=0; i<n; i++) {scanf("%d",&w[i]);}for(int i=0; i<(1<<n); i++) {for(int j=0; j<n; j++) {if(i&(1<<j)) sum[i]+=w[j];}}dfs((1<<n)-1);double ans=-1;for(int j=0; j<tree[(1<<n)-1].size(); j++) {ans=max(ans,tree[(1<<n)-1][j].x+tree[(1<<n)-1][j].y);}printf("%.16lf\n", ans);}return 0;
}刘汝佳代码+注释：
// UVa1354 Mobile Computing
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;struct Tree {double L, R; // distance from the root to the leftmost/rightmost pointTree():L(0),R(0) {}
};const int maxn = 6;int n, vis[1<<maxn]; //vis[]: 该子集是否已经有过
double r, w[maxn], sum[1<<maxn]; //r: 房间宽 w[]: 石头的重量 sum[]: 第i个子集的总重量
vector<Tree> tree[1<<maxn]; //tree[][]: 第i个子树的根节点到两边最远距离的可能值 void dfs(int subset) {if(vis[subset]) return; //曾访问过 vis[subset] = true;bool have_children = false;for(int left = (subset-1)? left; left = (left-1)&subset) { //枚举左边的子集 have_children = 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++) //计算tree[subset][] for(int j = 0; j < tree[right].size(); j++) {Tree t;t.L = max(tree[left][i].L + d1, tree[right][j].L - d2);t.R = max(tree[left][i].R - d1, tree[right][j].R + d2);if(t.L + t.R < r) tree[subset].push_back(t);}}if(!have_children) tree[subset].push_back(Tree()); //叶子节点
}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，书中190面有解释 sum[i] = 0;tree[i].clear();for(int j = 0; j < n; j++)if(i & (1<<j)) sum[i] += w[j];}int root = (1<<n)-1; //初始集合为n个1 memset(vis, 0, 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);printf("%.16lf\n", ans);}return 0;
}