[poj] 3977 Subset || 折半搜索MITM-白红宇

[poj] 3977 Subset || 折半搜索MITM

阅读量：5320 次

发布时间：2019-06-14

本文共 1460 字，大约阅读时间需要 4 分钟。

给定N个整数组成的数列(N<=35)，从中选出一个子集，使得这个子集的所有元素的值的和的绝对值最小，如果有多组数据满足的话，选择子集元素最少的那个。

n<=35，所以双向dfs的O(2^(n/2))可以直接解决问题。因为会爆空间，所以枚举前一半的二进制状态来完成dfs，并用map记录每个状态所用的个数，然后枚举后一半的状态在map中找第一个大于等于他的和第一个小于他的，比较这两个答案。

注：long long 没有自带的abs，并且在define里要多打括号，因为优先度……

#include
    
     #include
     #define abs(x) ((x)>0?(x):-(x))typedef long long ll;using namespace std;ll n,a[40],ans,sum;int cnt;map 
      
        mp;map 
       
         :: iterator qwq;ll read(){    ll ans=0,fu=1;    char j=getchar();    for (;(j<'0' || j>'9') && j!='-';j=getchar()) ;    if (j=='-') j=getchar(),fu=-1;    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';    return ans*fu;}int main(){    while (~scanf("%lld",&n) && n)    {    mp.clear();    ans=0;    cnt=0;    for (int i=1;i<=n;i++)        a[i]=read();    ans=abs(a[1]);    cnt=1;    for (int i=1,j,now,count;i<(1<<(n/2));i++)    {        sum=0;        j=i;        now=0;        count=0;        while (j)        {        if (j&1)            sum+=a[now+1],count++;        j>>=1;        now++;        }        if (abs(sum)
        
         >=1;        now++;        }        if (abs(sum)
         
          first; nw=abs(nw); if (nw
          
           second+count; } else if (nw==ans) cnt=min(cnt,qwq->second+count); } if (qwq!=mp.begin()) { qwq--; nw=sum+qwq->first; nw=abs(nw); if (nw
           
            second+count; } else if (nw==ans) cnt=min(cnt,qwq->second+count); } } printf("%lld %d\n",ans,cnt); } return 0;}

转载于:https://www.cnblogs.com/mrha/p/8017975.html

你可能感兴趣的文章