a: Baby Coins
Time Limit: 1 Sec Memory Limit: 128 MBDescription
Baby 今天清点自己的百宝箱啦,箱子里有 n 种硬币,硬币的面值分别是:val[1],val[2],...,val[n],每种面值的硬币都恰好有 2 个。Baby 实在闲的太无聊了,他想从他所拥有的硬币中选出若干个,使得面值之和为 k。那么他的目标能否实现呢 ~
Input
每一组数据第一行都包含两个数字 n(n≤18),k(1≤k≤1e9)。n 代表箱子中所包含的硬币种数,k 代表 Baby 需要组成的金钱数额。接下来的一行代表 val[1],val[2],......,val[n]。(1≤val[i]≤ 1e7)
Output
如果Baby能组成金钱数额k,请输出Yes,否则输出No。
Sample Input
22 103 43 91 2 10
Sample Output
Case 1: YesCase 2: No 折半枚举,先假设每种硬币只能选一次,枚举出所有可能性的和存到一个数组里(O(n*2^n)),然后把数组排序二分查找,比如一种可能性是a[i],那我们只要看k-a[i]是不是也在这个数组里就行了。
1 #include2 #include 3 using namespace std; 4 #define rd(a) scanf("%d",&a) 5 #define rep(i,a,b) for(int i=(a);i<=(b);i++) 6 int v[25],a[300000]; 7 int main(){ 8 int T; 9 rd(T);10 rep(tt,1,T){11 int n,k;12 rd(n);rd(k);13 for(int i=0;i
经过大佬指点之后发现还可以换一种思路枚举,这里我们把硬币平均分成前后两组,每一组分别枚举取0,1,2枚硬币的状态(O(n*3^(n/2))),然后在前后两组用二分找是否有和为k的就行了。
1 #include2 #include 3 using namespace std; 4 #define rd(a) scanf("%d",&a) 5 #define rep(i,a,b) for(int i=(a);i<=(b);i++) 6 int v[25],a[20000],b[20000],sum,pow3[20]={ 1}; 7 bool judge(int n,int k){ 8 if(sum =0;j--){13 while(t>=pow3[j])14 tot+=v[j],t-=pow3[j];15 }16 if(tot==k)return 1;17 if(tot =n/2;j--){22 while(t>=pow3[j-n/2])23 tot+=v[j],t-=pow3[j-n/2];24 }25 if(tot==k)return 1;26 if(tot