Baby Coins

http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4432

题解：二分折半查询。每种硬币有三种选择：选择其中一个，选择其中两个，不选择。
因此共有3^18 种，对总的方案折半，以其中一半为基础，对另一半二分查询是
否存在可能使得构成k。

C++版本一

#include <stdio.h>
#include <set>
std::set<int> st1, st2;
int a[20];

void dfs(int R, int id, int sum, std::set<int> &st){
    if (id == R){
        st.insert(sum);
        return;
    }
    dfs(R, id+1, sum, st);
    dfs(R, id+1, sum+a[id], st);
    dfs(R, id+1, sum+2*a[id], st);
}
bool check(int K){
    for(std::set<int> ::iterator it = st1.begin(); it != st1.end(); it ++){
        if(st2.find(K-*it) == st2.end()) continue;
        return true;
    }
    return false;
}

int main(){
//    freopen("baby_coins.in", "r", stdin);
//    freopen("baby_coins.out", "w", stdout);
    int T, n, K;
    int ica = 1;
    scanf("%d", &T);
    while(T --){
        scanf("%d%d", &n, &K);
        for(int i = 0; i < n; i ++){
            scanf("%d", &a[i]);
        }
        int ok = false;
        if(n == 1){
            if(a[0] == K || a[0]*2 == K) ok = 1;
        }else{
            dfs(n/2, 0, 0, st1);
            dfs(n, n/2, 0, st2);
            ok = check(K);
        }
        printf("Case %d: %s\n", ica ++, ok ? "Yes":"No");
        st1.clear();
        st2.clear();
    }
    return 0;
}

C++版本二

新思路，我发现上面的方法还是太慢了，基本上要跑100-300ms

如果我们把第二次枚举和查找结合，加上C++的逻辑判断机制，可以大大减少时间到100ms以内

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=20;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,ans;
set<int> st;
int a[N];
void dfs1(int R, int id, int sum){
    if (id == R){
        st.insert(sum);
        return;
    }
    dfs1(R, id+1, sum);
    dfs1(R, id+1, sum+a[id]);
    dfs1(R, id+1, sum+2*a[id]);
}
bool dfs2(int R, int id, int sum){
    if (id == R){
        if(st.find(k-sum) != st.end())
                return true;
        return false;
    }
    return dfs2(R, id+1, sum)||dfs2(R, id+1, sum+a[id])||dfs2(R, id+1, sum+2*a[id]);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    scanf("%d",&t);
    int T=0;
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        ans=0;
        if(n == 1){
            if(a[0] == k || a[0]*2 == k) ans = 1;
        }else{
            dfs1(n/2, 0, 0);
            ans=dfs2(n, n/2, 0);
        }
        if(ans){
            cout << "Case "<<++T<<": Yes" << endl;
        }else{
            cout << "Case "<<++T<<": No" << endl;
        }
        st.clear();
    }
    //cout << "Hello world!" << endl;
    return 0;
}

即使这样依然不是最快的的，大佬已经把时间压缩到56ms，23333