【bzoj1042】硬币购物

  • 本文为博主原创，未经许可不得转载

看到只有四种面额的硬币，以及每种硬币数量的限制，很容易想到容斥

我们用f[i]表示总面额为i且不考虑数量限制的方案数

则f[i]可以预处理出来

容斥时只需要令不合法的硬币数量为d[i]+1，然后计算f[s-(d[i]+1)*c[i]]即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define FILE "read"
typedef long long ll;
using namespace std;
const int MAXN=(int)1e5,D=50;
int s,a[10],c[10],d[10];
ll f[MAXN+D];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void pre(){
	f[0]=1;
	for(int i=1;i<=4;++i)
		for(int j=c[i];j<=MAXN;++j)
			f[j]+=f[j-c[i]];
}
void solve(){
	ll ans=0;
	for(int i=1;i<=4;++i)  d[i]=read();  s=read();
	for(int i=0;i<(1<<4);++i){
		int cnt=0,temp=s;
		for(int j=1;j<=4;++j)if((1<<(j-1))&i)a[++cnt]=j;
		for(int j=1;j<=cnt;++j) temp-=(d[a[j]]+1)*c[a[j]];
		if(temp<0)  continue;
		ans+=(cnt&1)?-f[temp]:f[temp];
	}
	printf("%lld\n",ans);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	for(int i=1;i<=4;++i)  c[i]=read();  pre();
	for(int T=read();T;--T)  solve();
	return 0;
}

本文标题:【bzoj1042】硬币购物

文章作者:chty

发布时间:2017年03月12日 - 19时53分

最后更新:2018年03月02日 - 17时33分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,