hdu 4016 Magic Bitwise And Operation 搜索

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4016
题目意思：从n个数中挑选m个数，使得这m个数按位与之后结果最小，输出最小值。
For example, there are three integers 5, 6 and 7. You are asked to pick two of them. Your possible strategy is (5, 6), (5, 7) or (6, 7). The values when do bitwise and all the picked numbers together are as follows:
5 and 6 = 4
5 and 7 = 5
6 and 7 = 6
The smallest one is 4.
剪枝：
1.从当前值开始，如果选上剩下的所有，也不能小于已得最优值的话，返回。这里可以先进行一下预处理，即逆序与一下， 暂存结果。这样可以减到178ms。
2.最优值不用等到累积选到k数才更新，而是不断更新，因为与运算结果比原来两个都小，所以这也是一个剪枝。
3.预处理，从小到大排序，可想而知，先选小的，得到的最优值更接近于结果，是个强剪枝。

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=41;

const long long MAX=0x7fffffffffffffff;

int t,c,n,k;

long long a[N],ans;
long long b[N];
void dfs(int t,int d,long long num)//t表示下标 d表示取元素个数 num为上次计算最小值
{
    if (ans>num)ans=num;//2剪枝
    if (d==k||t==n+1)return;
    long long s=num;
    s&=b[t];
    if (s>=ans)return;//1剪枝
    dfs(t+1,d+1,num&a[t]);
    dfs(t+1,d,num);
}

int main()
{
    scanf("%d",&t);
    c=0;
    while (t--)
    {
        printf("Case #%d: ",++c);
        scanf("%d%d",&n,&k);
        for (int i=1;i<=n;i++)
        {
            scanf("%I64d",&a[i]);
        }
        sort(a+1,a+n+1);
        b[n]=a[n];
        for (int i=n-1;i>=1;i--)//将逆序与预处理暂存
        {
            b[i]=a[i]&b[i+1];
        }
        ans=MAX;
        dfs(1,0,MAX);
        printf("%I64d\n",ans);
    }

    return 0;

}