2018-03-23

折半枚举

指数级别的搜素，进行折半枚举之后，指数变为原来的一半

题目

HDU5616 Jam’s balance

题意

就是看给一定重量的砝码看能不能称出来

题解

最最开始想到的就是暴力枚举，时间复杂度为\(O(m3^n)\).
但是这样肯定会T啊。
于是就有了折半枚举这种操作，时间复杂度为\(O(m3^{\frac{n}{2}})\).

AC代码

1
2

它解

01背包：
正向枚举的时候，枚举了放砝码的情形。

再枚举一次，枚举不放砝码和减去砝码的情形，感觉还是很巧妙的。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20*100+10;
int n, m;
int weight[25];
bool bag[maxn];
void solve(){
    bag[0] = true;
    //包含了用这个砝码和不用这个砝码的情况
    for(int i=0; i<n; i++){
        for(int j=maxn; j>=weight[i]; j--){
            bag[j] |= bag[j-weight[i]];
        }
    }
    //反向减去砝码
    for(int i=0; i<n; i++){
        for(int j=weight[i]; j<maxn; j++){
            bag[j-weight[i]] |= bag[j];
        }
    }
}
int main(){
        int t;
        cin>>t;
        while(t--){
            memset(bag, 0, sizeof(bag));
            cin>>n;
            for(int i=0; i<n; i++) scanf("%d", &weight[i]);
            solve();
            cin>>m;
            for(int i=0; i<m; i++){
                int wei;
                cin>>wei;
                if(bag[wei]){
                    printf("YES\n");
                }
                else printf("NO\n");
            }
        }
    return 0;
}

未解决的问题

本文标题:折半枚举

文章作者:Babydragon

发布时间:2018-03-23, 20:22:09

最后更新:2018-03-23, 20:35:13

原始链接:http://baolintian.github.io/2018/03/23/折半枚举/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。