BZOJ 1042: [HAOI2008]硬币购物 (详解)(背包&am…
2018-06-17 20:53:50来源:未知 阅读 ()
题面:https://www.cnblogs.com/fu3638/p/6759919.html
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西,
请问每次有多少种付款方法。其中di,s<=100000,tot<=1000。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxs=100000;
ll ans,f[maxs+10];
int c[5],d[5],tot,s;
int main(){
scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&tot);
//完全背包预处理
f[0]=1;
for(int i=1;i<=4;i++)
for(int j=c[i];j<=maxs;j++)
f[j]+=f[j-c[i]];
for(int k=1;k<=tot;k++){
scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s);
ans=0;
for(int i=0;i<(1<<4);i++){
int rest=s,tt=i,num=0,pos=0;
while(tt){
pos++;//第几枚硬币
if(tt&1) rest-=c[pos]*(d[pos]+1),num++;//num->几枚有限制
tt>>=1;
}
if(rest<0) continue;
if(num&1) ans-=f[rest];
else ans+=f[rest];
}
printf("%lld\n",ans);
}
return 0;
}
参考:
https://blog.csdn.net/aarongzk/article/details/51511564
https://blog.csdn.net/doctor_godder/article/details/50071749
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:基于神念TGAM的脑波小车(2)
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 【做题笔记】P1042 乒乓球 2020-02-14
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash