題面：https://www.cnblogs.com/fu3638/p/6759919.html 硬幣購物一共有4種硬幣。面值分別為c1,c2,c3,c4。某人去商店買東西，去了tot次。每次帶di枚ci硬幣，買si的價值的東西， 請問每次有多少種付款方法。其中di,s<=100000,tot<=1 ...
題面：https://www.cnblogs.com/fu3638/p/6759919.html
硬幣購物一共有4種硬幣。面值分別為c1,c2,c3,c4。某人去商店買東西，去了tot次。每次帶di枚ci硬幣，買si的價值的東西，
請問每次有多少種付款方法。其中di,s<=100000,tot<=1000。
題解：首先考慮一個簡單的問題，如果去掉題目中對於個數的限制，即給你四種面值的的硬幣，問你有多少種方案能湊成 si的價值。欸我們瞬間發現這是個完全背包的裸題，那果斷亂搞。 首先我們做一遍完全背包，定義f[i]為湊成i價值的方案數。 接下來回到原題，我們發現題目加了一個di的限制，那怎麼辦呢（摸摸腦袋）。 經過冷靜的分析（查題解），發現這題可以用容斥原理亂搞。
通過容斥原理，我們得出ans=全部方案（不考慮限制（即f[ans]））-Σ一種面值超過限制的方案數+Σ兩種超限-Σ三種超限+Σ四種超限。 那麼如何求有幾種超過限制的方案數呢 以一種面值超過限制的方案數為例，那麼這一種（不妨設為第i種）至少用d[i]+1個，即產生c[i]*(d[i]+1)的價值。那麼剩下的s-c[i]*(d[i]+1)（記為rest） 就可以隨意取值，即為f[rest]種。
那麼兩種三種的就是f[rest](rest=s-Σc[i]*(d[i]+1))。 tip:枚舉方案可以用位運算。 P.S. 開long long!! 代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxs=100000;
ll ans,f[maxs+10];
int c[5],d[5],tot,s;
int main(){
scanf("%d%d%d%d%d",&c[1],&c[2],&c[3],&c[4],&tot);
//完全背包預處理
f[0]=1;
for(int i=1;i<=4;i++)
for(int j=c[i];j<=maxs;j++)
f[j]+=f[j-c[i]];
for(int k=1;k<=tot;k++){
scanf("%d%d%d%d%d",&d[1],&d[2],&d[3],&d[4],&s);
ans=0;
for(int i=0;i<(1<<4);i++){
int rest=s,tt=i,num=0,pos=0;
while(tt){
pos++;//第幾枚硬幣
if(tt&1) rest-=c[pos]*(d[pos]+1),num++;//num->幾枚有限制
tt>>=1;
}
if(rest<0) continue;
if(num&1) ans-=f[rest];
else ans+=f[rest];
}
printf("%lld\n",ans);
}
return 0;
}
參考：
https://blog.csdn.net/aarongzk/article/details/51511564
https://blog.csdn.net/doctor_godder/article/details/50071749
