查看原题请戳这里
看到这道题，最直观的就是对于每一种情况都跑一遍多重背包，然而这样做的话时间复杂度会变得非常奇妙……
首先，我们可以考虑每种钱的个数没有限制的方案数。很显然，我们可以直接跑一个完全背包。
那么，如果只有一种钱存在个数限制呢？
我们用$f[i]$表示支付金额$i$的方案数，那么$f[s]$就是硬币没有限制时支付的方案数。如果面值为$c[i]$的硬币的数量为$d[i]$，那么只用c[i]可以支付的最大金额就是$c[i]\times d[i]$。那么，如果我们先花掉$d[i]+1$张面额为$c[i]$的钱，然后再用这$4$种钱去支付剩余的金额，那么无论剩余金额的支付方案是什么，这个放案一定会使用至少$d[i]+1$张$c[i]$，即$c[i]$的使用数量一定会超出限制。
我们再来考虑这些钱全部有数量限制时的情况。
如果我们对于每一种钱都按上面的方案处理，那么对于某种即超出$c[i]$的限制，又超出$c[j]$限制的方案数，我们就会减两遍，所以这里我们需要容斥一下。
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long c[5],d[5],ans,tot,s,f[100005],k;
int main()
{
for(int i = 1; i <= 4; i++) scanf("%d",&c[i]); scanf("%d",&tot);
f[0] = 1;
for(int j = 1; j <= 4; j++)
for(int i = 1; i <= 100000; i++)
if(i >= c[j]) f[i] = f[i] + f[i - c[j]];
while(tot--)
{
for(int i = 1; i <= 4; i++) scanf("%d",&d[i]);
scanf("%d",&s);
ans = f[s];
for(int k = 15;k > 0; k--)
{
long long u = 0,o = k,now = 0,cnt = 0;
while(o > 0)
{
cnt++;
if(o & 1)
{
now = (d[cnt] + 1) * c[cnt] + now;
u ^= 1;
}
o >>= 1;
}
if(now > s) continue;
if(u) ans -= f[s - now];
else ans += f[s - now];
}
printf("%lld\n",ans);
}
return 0;
}
|
