Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

Luogu P1450 [HAOI2008]硬币购物 解题报告

P1450 [HAOI2008]硬币购物

共有 $4$ 种硬币。面值分别为 $c_1,c_2,c_3,c_4$。

某人去商店买东西,去了 $n$ 次,对于每次购买,他带了 $d_i$ 枚 $i$ 种硬币,想购买 $s$ 的价值的东西。请问每次有多少种付款方法。

解题思路:

容斥 + DP

挺牛逼的一道题,做了一天学到很多。

首先看到这个问题,根据经验发现可以通过多重背包解决,但是时间复杂度为 $O(ns^2)$,非常离谱。

我们先把问题分割成小问题

共有 $1$ 种硬币。面值为$c$ ,不限制使用次数。

那么这就是裸的无限背包,$O(n)$ 即可解决。

加上限制怎么做?直接背包肯定是不行的,我们考虑用总数减去反面。

即 满足条件的方案总数 = 方案总数 - 不满足条件的方案总数

那么问题就转化为了如何求不满足条件的方案总数。我们观察题目性质可以发现,如果我们取了 $d_i + 1$ 个硬币,那么接下来不论怎么取硬币都是非法方案。

所以我们可以想到,强制令体积为 $s - c_i * (d_i + 1)$ 那么所有方案都是非法的,转化为方程也就是

试图扩大下这个问题,发现如果我们直接去掉 $c_i * (d_i + 1)$ 还会把其他部分的合法方案给去掉。这里设第 $i$ 种硬币的不合法方案集合为 $A_i$,那么我们就是要求

这就是一个很明显的容斥问题了。

根据容斥原理,我们可以得出

现在还有一个问题,如何求 $|A_1 \cap A_2|$ ?

还是类似刚才的做法,如果要让这种方案成立,我们就强制把两个硬币全部扣去,即 $s - (c_i \times (d_i + 1)) - (c_j \times (d_j + 1)))$

同样可以拓展到 $n$ 个的情况。

对于这个问题,我们在问题最开始时先预处理一遍没有限制的选择方案 $f$,然后每次求并集直接算 $f_{s - (c_i \times (d_i + 1)) - (c_j \times (d_j + 1))}$

所以这里我们可以通过枚举子集来快速求解,比如说 5 对应的 4 位二进制表示为 0110
,我们就认为这里是要求 $|A_2 \cap A_3|$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 0;i < 16;++i) {
ll siz = 0,k = 0,tmp = 0,tot = 1;
ll p = i;
while (p) {
if (p & 1) {
tmp += c[tot] * (d[tot] + 1);
//计算c_i * (d_i + 1)
++siz;
//统计当前有多少个
}
++tot,p >>= 1;
}
if (siz % 2) k = -1;
else k = 1;
//奇加偶减
if (s - tmp < 0) continue;
//排除非法方案
ans += k * f[s-tmp];
}

于是这题就做完了。

总结:

  1. 如果正面思考不通,尝试用整体去掉反面来计算答案
  2. 统计方案时出现重复部分,用容斥原理来处理
  3. 所谓“奇加偶减”,其实是第 $i$ 项的运算和第 $i-1$ 项运算符相反,主要确定第 1 项是啥
  4. 进行第 1 步时,如果发现哪里 RE 了,考虑排查边界问题。

代码:

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
read(c[1],c[2],c[3],c[4],n);
f[0] = 1;
for (int i = 1;i <= 4;++i) {
for (int j = c[i];j <= N;++j) {
f[j] += f[j - c[i]];
}
}
while (n--) {
ll ans = 0;
read(d[1],d[2],d[3],d[4],s);
for (int i = 0;i < 16;++i) {
ll siz = 0,k = 0,tmp = 0,tot = 1;
ll p = i;
while (p) {
if (p & 1) tmp += c[tot] * (d[tot] + 1),++siz;
++tot,p >>= 1;
}
if (siz % 2) k = -1;
else k = 1;
//printf("%lld\n",tmp);
if (s - tmp < 0) continue;
ans += k * f[s-tmp];
}
printf("%lld\n",ans);
}
return 0;