首页 > 代码库 > 子集枚举好题UVA1354
子集枚举好题UVA1354
题目
分析:枚举子集以及关于该子集的补集,然后用子集去暴力构造一颗二叉树,注意左边的最远距离不一定来自于左子树,右边的最远距离也不一定来自于右子树
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 #include "vector" 6 using namespace std; 7 const int maxn=15; 8 int T,s,vis[1<<maxn]; 9 double r,w[maxn],sum[1<<maxn]; 10 struct Tree{ 11 double L,R; 12 Tree():L(0),R(0){}; 13 }; 14 vector<Tree> tree[1<<maxn]; 15 16 void dfs(int subset){ 17 if(vis[subset]) return; 18 vis[subset]=1; 19 int flag=0; 20 for(int left=(subset-1)⊂left;left=(left-1)&subset){ 21 flag=1; 22 int right=left^subset; 23 double d1=sum[right]/sum[subset]; 24 double d2=sum[left]/sum[subset]; 25 dfs(left); dfs(right); 26 for(int i=0;i<tree[left].size();i++){ 27 for(int j=0;j<tree[right].size();j++){ 28 Tree t; 29 t.L=max(tree[left][i].L+d1,tree[right][j].L-d2); 30 t.R=max(tree[left][i].R-d1,tree[right][j].R+d2); 31 if(t.L+t.R<r) tree[subset].push_back(t); 32 } 33 } 34 } 35 if(!flag) tree[subset].push_back(Tree()); 36 } 37 int main() 38 { 39 scanf("%d",&T); 40 while(T--){ 41 scanf("%lf%d",&r,&s); 42 for(int i=0;i<s;i++) 43 cin>>w[i]; 44 for(int i=0;i<1<<s;i++){ 45 tree[i].clear(); 46 sum[i]=0; 47 for(int j=0;j<s;j++){ 48 if(i&(1<<j)){ 49 sum[i]+=w[j]; 50 } 51 } 52 } 53 int root=(1<<s)-1; 54 memset(vis,0,sizeof(vis)); 55 dfs(root); 56 double ans=-1; 57 for(int i=0;i<tree[root].size();i++) 58 ans=max(ans,tree[root][i].L+tree[root][i].R); 59 if(ans==-1) 60 printf("-1\n"); 61 else 62 printf("%.10lf\n",ans); 63 } 64 }
子集枚举好题UVA1354
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。