hdu Jersey Politics(dfs)

题意:把奶牛分成3组,只要有两组大于1/2量,用深搜剪枝

hdu  Jersey Politics(dfs)
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=220;
 7 struct node
 8 {
 9     int key,id;
10     bool operator <(const node &xx)const
11     {
12         return key>xx.key;
13     }
14 }data[maxn];
15 
16 bool cmp(const node &p,const node &q)
17 {
18     return p.key<q.key;
19 }
20 int sum[maxn],n;
21 bool use[maxn],flag;
22 void dfs(int t,int ret,int ans)
23 {
24     if(flag) return ;
25     if(ret==n)
26     {
27         if(ans>n*500&&sum[n+n]-ans>n*500)
28         {
29             for(int i=1;i<=n+n;i++)
30             if(use[i])
31             printf("%d\n",data[i].id);
32             for(int i=1;i<=n+n;i++)
33             if(!use[i])
34             printf("%d\n",data[i].id);
35             flag=true;
36         }
37         return ;
38     }
39     if(ans+sum[t]-sum[t-(n-ret)]<=n*500) return ;
40     if(sum[n+n]-(ans+sum[n-ret])<=n*500) return ;
41     for(int i=t;i>=n-ret;i--)
42     {
43         use[i]=1;
44         dfs(i-1,ret+1,ans+data[i].key);
45         use[i]=0;
46     }
47 }
48 
49 int main()
50 {
51     scanf("%d",&n);
52     for(int i=1;i<=n*3;i++)
53     {
54         scanf("%d",&data[i].key);
55         data[i].id=i;
56     }
57     sort(data+1,data+1+n*3);
58     sort(data+1,data+1+n+n,cmp);
59     sum[0]=0;
60     for(int i=1;i<=n+n;i++)
61     sum[i]=sum[i-1]+data[i].key;
62     flag=0;
63     memset(use,0,sizeof(use));
64     dfs(n+n,0,0);
65     for(int i=n+n+1;i<=n*3;i++)
66     printf("%d\n",data[i].id);
67     return 0;
68 }
View Code

hdu Jersey Politics(dfs)

上一篇:操作系统性能分析与优化V1.0


下一篇:如何在sharepoint里通过correlation id查找详细的错误信息