翘了3节课来A这道题，最后还超时了，也是蛮拼的。。
没做出来主要一个方面就是不会一个二进制数子集的枚举
这里上一下代码：
for(int S0 = S; S0; S0 = (S0 – 1) & S){}这里S0就是S的子集了~！
题目的思路就是枚举所有情况，，注意记忆化【话说这题学到了不少】
#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;//枚举二叉树的形状const int maxn = 8;const int maxd = (1 << 8);int n;double ww;int w[maxn];int sum[maxd];int vis[maxd];double ret;struct Node{double l,r;Node(double ll,double rr):l(ll),r(rr){};};vector<Node>node[maxd];void debug(int v){if(!v){puts(""); return;}debug(v / 2);printf("%d",v % 2);}bool judge(int S){for(int i = 0; i < n; i++)if(S == (1 << i))return true;return false;}void dfs(int S){//枚举now的子集if(vis[S]) return;vis[S] = 1;if(judge(S)){node[S].push_back(Node(0,0));return;}//printf("%d\n",S);for(int S0 = S; S0; S0 = (S0 – 1) & S)if(S0 != S){int l = S0;int r = S0 ^ S;dfs(l); dfs(r);//枚举左右的子集for(int i = 0; i < node[l].size(); i++)for(int j = 0; j < node[r].size(); j++){double l1 = 1.0 * sum[r] / (sum[l] + sum[r]);double r1 = 1.0 * sum[l] / (sum[l] + sum[r]);double l2 = min(-l1 + node[l][i].l,r1 + node[r][j].l);double r2 = max(-l1 + node[l][i].r,r1 + node[r][j].r);//printf("[%d]: %.2f %.2f\n",S,l2,r2);node[S].push_back(Node(l2,r2));}}return;}int main(){int T;scanf("%d",&T);while(T–){scanf("%lf%d",&ww,&n);ret = -1;memset(vis,0,sizeof(vis));for(int i = 0; i < n; i++)scanf("%d",&w[i]);for(int i = 0; i < (1 << n); i++){sum[i] = 0;node[i].clear();for(int j = 0;j < n; j++){if(i & (1 << j)){sum[i] += w[j];}}}int S = (1 << n) – 1;dfs(S);//printf("%d\n",node[S].size());for(int i = 0; i < node[S].size(); i++){double d = node[S][i].r – node[S][i].l;//printf("%.4f %.4f\n",node[S][i].r,node[S][i].l);if(d <= ww)ret = max(ret,d);}if(ret < 0) printf("-1\n");elseprintf("%.16f\n",ret);}return 0;}
代替你主持夕阳的葬礼。
