Bzoj 1042: [HAOI2008]硬币购物 容斥原理,动态规划,背包dp

1042: [HAOI2008]硬币购物

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1747  Solved: 1015
[Submit][Status][Discuss]

Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。

Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

HINT

数据规模

di,s<=100000

tot<=1000

Source

 题解:
容斥原理+动态规划
f[i]表示四种硬币个数没有限制的付款方案数。(求f[i]就是个完全背包)
ans=不限定的方案数-(硬币1超过的方案数+硬币2超过的方案数+硬币3超过的方案数+硬币4超过的方案数)+(硬币1,2超过的方案数………………)-(硬币1,2,3超过的方案数)+(硬币1,2,3,4都超过的方案数)
超过的方案数:
     例如:要算硬币1超过的方案数,那么我们就要让硬币1超过d[1],即为d[1]+1,则剩余价值为s-(d[1]+1)*c[1]。
具体见程序:
 #include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define LL long long
LL S,c[],d[],f[MAXN+];
LL read()
{
LL s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
LL F(LL A,LL B,LL C,LL D)
{
LL ans=S;
if(A!=)ans-=(d[]+)*c[];
if(B!=)ans-=(d[]+)*c[];
if(C!=)ans-=(d[]+)*c[];
if(D!=)ans-=(d[]+)*c[];
if(ans<)return ;
return f[ans];
}
int main()
{
LL i,j,sum,tot;
for(i=;i<=;i++)c[i]=read();tot=read();
f[]=;
for(i=;i<=;i++)
{
for(j=c[i];j<=MAXN;j++)f[j]+=f[j-c[i]];
}
while(tot--)
{
for(i=;i<=;i++)d[i]=read();S=read();
sum=;
sum+=F(,,,);
sum-=F(,,,);
sum-=F(,,,);
sum-=F(,,,);
sum-=F(,,,);
sum+=F(,,,);
sum+=F(,,,);
sum+=F(,,,);
sum+=F(,,,);
sum+=F(,,,);
sum+=F(,,,);
sum-=F(,,,);
sum-=F(,,,);
sum-=F(,,,);
sum-=F(,,,);
sum+=F(,,,);
printf("%lld\n",sum);
}
return ;
}
上一篇:java.sql.SQLException: Incorrect string value:


下一篇:C/C++迭代器使用具体解释