首页 > 代码库 > bzoj1042: [HAOI2008]硬币购物
bzoj1042: [HAOI2008]硬币购物
好神的容斥原理
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longint read(){ int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x;}const int nmax=1e5+5;ll f[nmax];int c[5],d[5];int main(){ rep(i,1,4) c[i]=read(); f[0]=1; rep(i,1,4) rep(j,c[i],100000) f[j]+=f[j-c[i]]; int n=read(); rep(i,1,n){ rep(j,1,4) d[j]=read(); int m=read(),cnt,tmp;ll ans=0; rep(j,0,15){ cnt=0;tmp=m; for(int k=j,t=1;k;k>>=1,t++) if(k&1) tmp-=c[t]*(d[t]+1),cnt++; if(tmp<0) continue; if(cnt&1) ans-=f[tmp]; else ans+=f[tmp]; } printf("%lld\n",ans); } return 0;}
1042: [HAOI2008]硬币购物
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2054 Solved: 1206
[Submit][Status][Discuss]
Description
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买s
i的价值的东西。请问每次有多少种付款方法。
Input
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s,其中di,s<=100000,tot<=1000
Output
每次的方法数
Sample Input
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900
3 2 3 1 10
1000 2 2 2 900
Sample Output
4
27
27
HINT
Source
bzoj1042: [HAOI2008]硬币购物
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。