首页 > 代码库 > bzoj1042--容斥原理+完全背包

bzoj1042--容斥原理+完全背包

2024-09-01 19:44:43   216人阅读

题目大意：

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

思路：
先用完全背包求出如果每种硬币可以用无数次的方案数，再容斥一下就好了。

具体看代码。

代码：

技术分享 
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 #define ll long long
 7 int i,j,k,n,m,tot,c[4],d[4],s;
 8 ll f[100001],ans;
 9 bool b[4];
10 inline ll S(){
11     int tmp=s;
12     for(int i=0;i<4;i++)if(b[i])tmp-=c[i]*(d[i]+1);
13     if(tmp<0)return 0;else return f[tmp];
14 }
15 inline void dfs(int x,int sum){
16     if(x==4){
17         if(sum==0)return;
18         if(sum&1)ans-=S();else ans+=S();
19         return;
20     }
21     dfs(x+1,sum);
22     b[x]=1;
23     dfs(x+1,sum+1);
24     b[x]=0;
25 }
26 int main()
27 {
28     for(i=0;i<4;i++)scanf("%d",&c[i]);scanf("%d",&tot);
29     for(f[0]=1,i=0;i<4;i++)
30     for(j=c[i];j<=100000;j++)
31     f[j]+=f[j-c[i]];
32     while(tot--){
33         for(i=0;i<4;i++)scanf("%d",&d[i]);
34         scanf("%d",&s);
35         ans=f[s];
36         dfs(0,0);
37         printf("%lld\n",ans);
38     }
39     return 0;
40 }
bzoj1042

 

bzoj1042--容斥原理+完全背包


联系
我们