hdu Jersey Politics（dfs）

港控/mmm° 2022-01-05 15:34 215阅读 0赞

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/sdau--codeants/p/3534761.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/9588ad54e3f0446288a0d2f7ae4b294b.png