#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef long long LL; #define CLR(x,y) memset((x),(y),sizeof((x))) #define FOR(x,y,z) for(int (x)=(y);(x)<(z);(x)++) #define FORD(x,y,z) for(int (x)=(y);(x)>=(z);(x)--) #define FOR2(x,y,z) for((x)=(y);(x)<(z);(x)++) #define FORD2(x,y,z) for((x)=(y);(x)>=(z);(x)--) const int maxs = 10; int s,vis[maxs]; double r,maxres,w[maxs],lenl[maxs],lenr[maxs]; int qhy(int cur){ if(cur == s - 1){//枚举完成, FOR(i,0,s){ if(!vis[i]){//剩下那个节点就是 //更新信息 double tmp = lenl[i] + lenr[i]; if(tmp > maxres && r > tmp) maxres = tmp; return 0; } } } //枚举两个节点 FOR(n,0,s){ if(vis[n]) continue; FOR(m,0,s){ if(n != m && !vis[m]){ //合并两个节点,并把合并后的点,保存在m对应的位置 vis[n] = 1; double tmp = w[m],a = w[m] / (w[n] + w[m]),b = 1. - a; w[m] = w[n] + w[m]; double tmpl = lenl[m],tmpr = lenr[m]; lenl[m] = max(lenl[n] + a,lenl[m] - b); lenr[m] = max(lenr[m] + b,lenr[n] - a); qhy(cur + 1); //恢复m点 lenl[m] = tmpl; lenr[m] = tmpr; w[m] = tmp; vis[n] = 0; } } } return 0; } int main(){ int cntcase; scanf("%d",&cntcase); while(cntcase--){ scanf("%lf%d",&r,&s); FOR(i,0,s){ scanf("%lf",&w[i]); } //初始化 CLR(vis,0);CLR(lenl,0);CLR(lenr,0);maxres = -1.0; qhy(0); printf("%.14f\n",maxres); } return 0; } |
[2016-02-22][UVA][1354][Mobile Computing]
原文：http://www.cnblogs.com/qhy285571052/p/5207992.html