首页 > 代码库 > 【bzoj4800】[Ceoi2015]Ice Hockey World Championship 折半搜索
【bzoj4800】[Ceoi2015]Ice Hockey World Championship 折半搜索
题目描述
有n个物品，m块钱，给定每个物品的价格，求买物品的方案数。
输入
第一行两个数n，m代表物品数量及钱数
第二行n个数，代表每个物品的价格
n<=40，m<=10^18
输出
一行一个数表示购买的方案数
（想怎么买就怎么买，当然不买也算一种）
样例输入
5 1000
100 1500 500 500 1000
样例输出
8
题解
裸的折半搜索meet-in-the-middle
由于直接爆搜肯定会TLE，考虑把整个序列分成左右两部分，对于每部分求出它所有可以消耗钱数的方案。然后考虑左右组合怎么能够使总钱数不超过m。
考虑枚举右边序列的某钱数，那么左边的钱数要求就是不超过m-右边钱数。所以可以对左边序列排序，然后再二分查找即可知道不超过m-右边钱数的数的个数。把这个个数累加到答案中即可。
时间复杂度$O(2^{\frac n2}*\log 2^{\frac n2}=2^{\fracn2}*n)$。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;ll a[1 << 21] , b[1 << 21] , w[50] , m;int ta , tb;void dfs(int x , int n , ll now , ll *a , int &ta){ if(now > m) return; if(x > n) { a[++ta] = now; return; } dfs(x + 1 , n , now , a , ta) , dfs(x + 1 , n , now + w[x] , a , ta);}int main(){ int n , i; ll ans = 0; scanf("%d%lld" , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &w[i]); dfs(1 , n >> 1 , 0 , a , ta); dfs((n >> 1) + 1 , n , 0 , b , tb); sort(a + 1 , a + ta + 1); for(i = 1 ; i <= tb ; i ++ ) { if(m - b[i] >= a[ta]) ans += ta; else ans += upper_bound(a + 1 , a + ta + 1 , m - b[i]) - a - 1; } printf("%lld\n" , ans); return 0;}
【bzoj4800】[Ceoi2015]Ice Hockey World Championship 折半搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。