题意:有n杯盐溶液,给定每杯里面盐的质量以及盐溶液的质量。问你有多少种方案选择一个子集,使得集合里面的盐溶液倒到一个被子里面以后,浓度为A/B。

折半枚举,暴力搜索分界线一侧的答案数,跨越分界线的答案,一侧用map存下来,枚举另一侧去统计。

#include<cstdio>
#include<map>
using namespace std;
typedef long long ll;
ll ans;
int n,a,b,m[39],t[39];
map<ll,int>ma;
void dfs(int op,int cur,int goal,int dep,ll A,ll B){
if(dep!=0){
if(A*(ll)b==B*(ll)a){
++ans;
}
if(op==0){
++ma[(ll)b*A-(ll)a*B];
}
else{
ans+=(ll)ma[(ll)a*B-(ll)b*A];
}
}
for(int i=cur;i<=goal;++i){
dfs(op,i+1,goal,dep+1,A+(ll)m[i],B+(ll)t[i]);
}
}
int main(){
// freopen("g.in","r",stdin);
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;++i){
scanf("%d%d",&m[i],&t[i]);
}
dfs(0,1,n/2,0,0,0);
dfs(1,n/2+1,n,0,0,0);
printf("%lld\n",ans);
return 0;
}

最新文章

  1. EntityFramework.Extended 支持 MySql
  2. flex-布局,轻松制作移动端网页
  3. keil l251 command summary --Lib
  4. 获取android SDCard存储大小
  5. JAVA敏捷开发环境搭建(转载)
  6. javascript Date 函数的坑
  7. PHP手机获取6为不反复验证码
  8. C++标准程序读书笔记-第三章错误和异常处理
  9. java基础系列--集合类库(一)
  10. LeetCode专题-Python实现之第26题:Remove Duplicates from Sorted Array
  11. ccflow表机构与运行机制(二次开发必看)
  12. Linux/Unix系统QA
  13. vue :基本语法格式
  14. P1433 吃奶酪 回溯法 优化
  15. 第二章 JavaScript文档(上)
  16. (转) Read-through: Wasserstein GAN
  17. JFinal Web开发学习(八)后台集成H-ui-admin前端框架
  18. Java中的forin语句
  19. expr命令总结
  20. 国家code和区号计算

热门文章

  1. JSP九大内置对象,七大动作,三大指令
  2. xrange和range的区别
  3. MySQL 8.0 正式版 8.0.11 发布:比 MySQL 5.7 快 2 倍
  4. linux===Ubuntu修改设备名称
  5. Tabular DataStream protocol 协议
  6. ES的优化布局
  7. HDU 6188 Duizi and Shunzi 贪心
  8. kivy安装
  9. udp调用connect有什么作用(转)
  10. JS实现判断滚动条滚到页面底部并执行事件的方法