博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ1042: [HAOI2008]硬币购物
阅读量:6295 次
发布时间:2019-06-22

本文共 2112 字,大约阅读时间需要 7 分钟。

这个相当神奇,用容斥原理做背包。

首先,我们要先处理出四种钞票都不限的方案数。

对于每一个询问,我们利用容斥原理,答案为:得到S所有超过数量限制的方案数-硬币1超过限制的方案数-硬币2超过限制的方案数-硬币3超过限制的方案数-硬币4超过限制的方案数+硬币1、2超过限制的方案数+…+硬币1、2、3、4均超过限制的方案数。

而对于每种方案数的求法,也非常简单:假设我们要求的是F[S],则硬币1超过限制(即硬币1取的个数≥d[1]+1,不考虑硬币2、3、4是否超过限制)时的方案数即为F[S-(d[1]+1)×c[1]]。

1 /************************************************************** 2     Problem: 1042 3     User: zhuohan123 4     Language: C++ 5     Result: Accepted 6     Time:44 ms 7     Memory:2132 kb 8 ****************************************************************/ 9  10 #include 
11 #include
12 #include
13 #include
14 using namespace std;15 int c[5];16 long long F[110000];17 struct{
long long operator[](int pos){
return pos<0?0:F[pos];}}f;18 int main(int argc, char *argv[])19 {20 int T;scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&T);21 F[0]=1;22 for(int i=1;i<=4;i++)23 for(int j=0;j<=100000;j++)24 if(j+c[i]<=100000)F[j+c[i]]+=F[j];25 while(T--)26 {27 int d[5],s;scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s);28 long long ans=f[s];29 ans-=f[s-(d[1]+1)*c[1]];30 ans-=f[s-(d[2]+1)*c[2]];31 ans-=f[s-(d[3]+1)*c[3]];32 ans-=f[s-(d[4]+1)*c[4]];33 ans+=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]];34 ans+=f[s-(d[1]+1)*c[1]-(d[3]+1)*c[3]];35 ans+=f[s-(d[1]+1)*c[1]-(d[4]+1)*c[4]];36 ans+=f[s-(d[2]+1)*c[2]-(d[3]+1)*c[3]];37 ans+=f[s-(d[2]+1)*c[2]-(d[4]+1)*c[4]];38 ans+=f[s-(d[3]+1)*c[3]-(d[4]+1)*c[4]];39 ans-=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[3]+1)*c[3]];40 ans-=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[4]+1)*c[4]];41 ans-=f[s-(d[1]+1)*c[1]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];42 ans-=f[s-(d[2]+1)*c[2]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];43 ans+=f[s-(d[1]+1)*c[1]-(d[2]+1)*c[2]-(d[3]+1)*c[3]-(d[4]+1)*c[4]];44 #ifdef ONLINE_JUDGE45 printf("%lld\n",ans);46 #else47 printf("%I64d\n",ans);48 #endif49 }50 return 0;51 }

 

转载于:https://www.cnblogs.com/zhuohan123/p/3284272.html

你可能感兴趣的文章
Python字符串处理函数
查看>>
防止DDOS***
查看>>
linux磁盘配额
查看>>
RHEL5 kickstart 安装小结
查看>>
【书签】格式化nginx.conf文件的工具
查看>>
shell安装samba服务
查看>>
学会分析网站空间日志
查看>>
SelectBox插件
查看>>
iptables总结
查看>>
Docker多台宿主机间的容器互联-centos7
查看>>
014、Linux下vim搜索与替换
查看>>
Thrift在windows下的使用
查看>>
3Mysql 的常用操作
查看>>
tomcat配备禁止url显示jsessionid
查看>>
IDE ,SAS,SATA,SCSI,SSD硬盘的主要区别
查看>>
Android的Framework分析---4硬件抽象HAL
查看>>
JS中字符串的相关操作
查看>>
Android版本介绍
查看>>
我的友情链接
查看>>
Exchange Server 2013之CAS服务器NLB负载均衡
查看>>