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

2022-12-30 13:21:15

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 ;

 }

码农公寓