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 DEBUGusing 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 DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%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

?

總結

以上是生活随笔為你收集整理的Baby Coins的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。