题意
硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。
题解
一眼看去一个多重背包dp...再一眼看去数据范围..1e5这样暴力背包就t了.
可以转换想法,假设硬币的枚数没有限制,这样在每一组样例中,用不限制的总的数量减掉不满足条件的数量。
而不限制硬币个数的数量就可以用多重背包求解即可
for(ll i = 0;i < 4;++i) for(ll j = 0;j < maxn;++j) if(j - c[i] >= 0) dp[j] += dp[j-c[i]];
接下来的问题就是如何找到针对每组数据不满足条件的付款方法,用总数减去即可。
考虑容斥定理,即,对于四种硬币可以看做四个集合,比如:即表示至少使用d0枚硬币买下东西,而满足条件情况的就是用所有情况减掉至少使用(d0+1)枚。但是考虑到,当减掉某两种不满足条件的情况时,我们将两集合的交集重复减掉了两遍,即需要使用容斥定理,将交集加回来。三种四种时同样。
而如何遍历这几种情况呢,可以将状态压缩为2进制表示,即1001就代表不满足第一种硬币和第四种硬币的情况,这样一共15种情况就可以表示为0001-1111 即遍历1-15,判断其二进制位即可。
code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 1e5 + 10; ll dp[maxn]; int main() { ll c[4]; ll t; for(ll i = 0;i < 4;++i)cin>>c[i]; cin>>t; dp[0] = 1; for(ll i = 0;i < 4;++i) for(ll j = 0;j < maxn;++j) if(j - c[i] >= 0) dp[j] += dp[j-c[i]]; for(ll i = 0;i < t;++i){ ll cnt[4]; for(ll i = 0;i < 4;++i) scanf("%d",&cnt[i]); ll s; cin>>s; ll res = dp[s]; for(ll i = 1;i <= 15;++i){ ll tmp = 0; ll now = 0; for(ll j = 0;j < 4;++j){ if((i >> j) & 1){ tmp++; now += (cnt[j] + 1) * c[j]; } } ll base = 1; if(tmp & 1) base = -1; if(s-now >= 0)res += base * dp[s - now]; } printf("%lld\n",res); } return 0; }