记录编号 |
463529 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[HAOI 2008]硬币购物 |
最终得分 |
100 |
用户昵称 |
Shirry |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.029 s |
提交时间 |
2017-10-24 12:00:44 |
内存使用 |
1.05 MiB |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,s,c[5],d[5];
long long f[100010];//f[j]:价值和为j的方案数
long long ans;
void init(){//预处理完全背包
f[0]=1;
for(int i=1;i<=4;i++)
for(int j=c[i];j<=100000;j++)
f[j]+=f[j-c[i]];
}
int main(){
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
for(int i=1;i<=4;i++)scanf("%d",&c[i]);
scanf("%d",&n);
init();
for(int k=1;k<=n;k++){
for(int i=1;i<=4;i++)scanf("%d",&d[i]);
scanf("%d",&s);
ans=0;
for(int i=0;i<(1<<4);i++){//容斥原理。1代表哪一种硬币超出.remember!!!i从0开始
int num=0,x=s;
for(int j=1;j<=4;j++){
if((i>>(j-1))&1)//取出从右向左数第j位
x-=(d[j]+1)*c[j],++num;//num统计有多少个1
}
if(x>=0){
if(num&1)ans-=f[x];
else ans+=f[x];
}
}
printf("%lld\n",ans);
}
return 0;
}