硬币购物
题目描述 Description
一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。 每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。
输入描述 Input Description
第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s
输出描述 Output Description
每次的方法数
样例输入 Sample Input
1 2 5 10 2
3 2 3 1 101000 2 2 2 900 样例输出 Sample Output
4
27 数据范围及提示 Data Size & Hint
di,s<=100000tot<=1000
背包+容斥即可。
#include#define ll long long#define maxn 100005using namespace std;ll f[maxn],ans;int a[10],ci[20],T,S;int n,m,tmp[105],tot[105];inline void dp(){ f[0]=1; for(int i=0;i<4;i++) for(int j=a[i];j<=100000;j++) f[j]+=f[j-a[i]]; tmp[0]=1; for(int i=1;i =tot[i]) ans+=tmp[i]*f[S-tot[i]]; } printf("%lld\n",ans); } return 0;}