洛谷P1450 [HAOI2008] 硬币购物 题解

题目链接：P1450 [HAOI2008] 硬币购物

题意：

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

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

输入格式：

输入的第一行是五个整数，分别代表 \(c_1,c_2,c_3,c_4, n\)。

接下来 \(n\) 行，每行有五个整数，描述一次购买，分别代表 \(d_1, d_2, d_3, d_4,s\)。

输出格式：

对于每次购买，输出一行一个整数代表答案。

数据范围：

对于 \(100\%\) 的数据，保证 \(1 \leq c_i, d_i, s \leq 10^5\)，\(1 \leq n \leq 1000\)。

首先可以想到朴素的背包dp，不过复杂度是 \(\mathcal{O}(4ns)\) 的。

考虑如果 \(d_i\) 足够大时，实际上我们不需要再去做 dp 了，只需要做一次 dp 存下来即可

不过这没有改变 \(d_i\) 可能不够的现实，因此考虑设 \(f_s\) 表示钦定花费为 \(s\) 的情况的方案数。

设性质 \(P_i~(1 \le i \le 4)\) 表示第 \(i\) 种硬币不够用，根据容斥我们只需要求出硬币不够用的情况即可。

显然第 \(i\) 种硬币不够用，意味着它需要至少 \(d_i+1\) 个，则 \(s \ge c_i(d_i+1)\) 。

于是剩余的 \(s - c_i(d_i+1)\) 可以随意分配，这相当于原问题的一个已解决的子问题。

那么我们只需要 dp 一遍就能得出答案了。

时间复杂度 \(\mathcal{O}(4s + 2^4n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int n, q, c[4], d[4]; ll res, f[N];
ll F(int x) { return x >= 0 ? f[x] : 0; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> c[0] >> c[1] >> c[2] >> c[3] >> q; f[0] = 1;
    rep(i, 0, 3) rep(j, c[i], N - 5) f[j] += f[j - c[i]];
    while(q--)
    {
        cin >> d[0] >> d[1] >> d[2] >> d[3] >> n;
        ++d[0]; ++d[1]; ++d[2]; ++d[3]; res = 0;
        rep(i, 0, 15)
        {
            static int s; s = n;
            rep(j, 0, 3) if((i >> j) & 1) s -= c[j] * d[j];
            res += __builtin_parity(i) ? -F(s) : F(s);
        }
        cout << res << '\n';
    }
    return 0;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/lydsy1042.html