BZOJ1042 [HAOI2008]硬币购物

题意

​  硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付款方法。

题解

​ 我们考虑用DP预处理出在没有硬币个数限制的情况下,到达si有多少种方法,这个显然用完全背包做。

​ 考虑对于有硬币限制。

答案 = 没有限制的情况 - 第一枚硬币超过限制 - 第二枚硬币超过限制 …… + 第一枚和第二枚硬币超过限制 + 第一枚和第三枚硬币超过限制 …… - 第一枚,第二枚,第三枚硬币超过限制 …… + 第一二三四枚硬币超过限制的情况。

​ 我们要计算第一枚硬币超过限制的情况,

​ 当第1种硬币超过限制时,只要要用到D[1]+1枚硬币,剩余的硬币可以任意分配,所以方案数为 F[ S – (D[1]+1)\times C[1] ],当且仅当(S – (D[1]+1)\times C[1])>=0,否则方案数为0。其余情况类似,每次询问只用问16次,所以询问的时间复杂度为O(1)。

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
42
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
namespace IO{
const int __buffsize = 1000000;char __buff[__buffsize];char *__buffS, *__buffT;
char getch(){if (__buffS == __buffT){__buffT = (__buffS = __buff) + fread(__buff,1,__buffsize,stdin);if (__buffS == __buffT) return EOF;}return *__buffS++;}
#define getch getchar
LL read(){LL T = 0,f = 1;char c = getch();while ((c<'0'||c>'9')&&c!='-') c=getch();if(c=='-')f=-1,c=getch();while (c>='0'&&c<='9'){T=((T<<1)+(T<<3))+c-48;c=getch();}return T*f;}
void write(int x){if(x < 0) putchar('0'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
void writeln(int x){write(x);puts("");}
};
using namespace IO;
LL f[100005];
LL c[10],d[10],s;
int main(){
for(int i=1;i<=4;i++) c[i]=read();
f[0] = 1;
for (int i=1;i<=4;i++)
for (int j=0;j<=100000 - c[i];j++)
f[j+c[i]] += f[j];
int tot = read();
while(tot--){
LL Ans = 0,res;int cnt;
for (int i=1;i<=4;i++) d[i]=read(); s = read();
for (int i=0;i<(1<<4);i++){
cnt = 0;
res = s;
for (int j=1;j<=4;j++){
cnt += ((i>>(j-1))&1);
res -= ((i>>(j-1))&1) * (d[j]+1) * c[j];
}
if (res >= 0)
if (cnt & 1) Ans -= f[res]; else
Ans += f[res];
}
printf("%lld\n",Ans);
}
}
文章目录
  1. 1. 题意
  2. 2. 题解