1042: [HAOI2008]硬幣購物

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?1446??Solved:?845
[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

題解：神題呦。

窩萌可以先算一個不考慮每種硬幣的數量限制的情況下的背包。如果超過了限制，只要要用到D[1]+1枚硬幣，剩余的硬幣可以任意分配，所以方案數為 F[ S – (D[1]+1)C[1] ]，當且僅當(S – (D[1]+1)C[1])>=0，否則方案數為0。套上容斥原理亂搞。

容斥原理的tip：奇負偶正（最開始是0）

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<stack> 6 #include<queue> 7 #include<cstring> 8 #define PAU putchar(' ') 9 #define ENT putchar('\n') 10 using namespace std; 11 typedef long long LL; 12 const int maxn=100000+10,maxm=5; 13 LL ans,f[maxn]; 14 int T,c[maxm],d[maxm]; 15 void dfs(int x,int k,int sum){ 16 if(sum<0)return; 17 if(x==5){if(k&1)ans-=f[sum];else ans+=f[sum];return;} 18 dfs(x+1,k+1,sum-(d[x]+1)*c[x]);dfs(x+1,k,sum);return; 19 } 20 void initpack(){ 21 f[0]=1; 22 for(int i=1;i<=4;i++) 23 for(int j=c[i];j<=100000;j++) 24 f[j]+=f[j-c[i]];return; 25 } 26 inline int read(){ 27 int x=0,sig=1;char ch=getchar(); 28 for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0; 29 for(;isdigit(ch);ch=getchar())x=10*x+ch-'0'; 30 return sig?x:-x; 31 } 32 inline void write(long long x){ 33 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 34 int len=0;long long buf[20];while(x)buf[len++]=x%10,x/=10; 35 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 36 } 37 int main(){ 38 for(int i=1;i<=4;i++)c[i]=read();T=read();initpack(); 39 for(int i=1;i<=T;i++){ 40 for(int k=1;k<=4;k++)d[k]=read(); 41 ans=0;dfs(1,0,read());write(ans);ENT; 42 } 43 return 0; 44 }

?

轉載于:https://www.cnblogs.com/chxer/p/4726930.html

總結

以上是生活随笔為你收集整理的BZOJ 1042 [HAOI2008]硬币购物的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。