lulaalu

字数

391 字

阅读时间

2 分钟

原题：硬币购物

题意

有四种硬币，面值为 $c_{1}, c_{2}, c_{3}, c_{4}$

$n$ 次问询，每次给出四面值硬币的数量 $d_{1}, d_{2}, d_{3}, d_{4}$ 和想买的东西的价值 $s$

求有多少种付款方式

思路

首先先通过一个[[完全背包]]求出所有 $s$ 对应的方法，再考虑数量

$d p [i]$ 表示不考虑数量的情况下买到 $i$ 价值的东西的付款方法

考虑[[../../../数据结构与算法/数学/容斥]]的思路，假定有4个2元硬币， $s = 20$ 先只用2元硬币

那么 $d p [20 - (4 + 1) * 2]$ 一定是不符合要求的数量，因为不能只用2元硬币补到20元

同理，如果是5个3元硬币，那么不合法的数量就是 $d p [20 - (4 + 1) * 2 - (5 + 1) * 3]$

根据容斥的基本原理加或者减

代码

CPP

int dp[S];
int c[4];
int n;
void build() {
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < 4; i++) {
        for (int j = c[i]; j < S; j++) {
            dp[j] += dp[j - c[i]];
        }
    }
}

int cnt[4], s;
int query() {
    int illegal = 0;
    // 用status表示当前计算那些硬币不符合要求的数量
    for (int status = 1; status < 16; status++) {
        int sta = -1;
        int t = s;
        for (int i = 0; i < 4; i++) {
            if ((status >> i) & 1 == 1) {
                sta = -sta;
                t -= (cnt[i] + 1) * c[i];
            }
        }
        if (t >= 0) illegal += dp[t] * sta;
    }
    return dp[s] - illegal;
}

signed main() {
    IOS;
    cin >> c[0] >> c[1] >> c[2] >> c[3] >> n;
    build();
    while (n--) {
        cin >> cnt[0] >> cnt[1] >> cnt[2] >> cnt[3] >> s;
        cout << query() << endl;
    }

    return 0;
}

贡献者

lulaalu

文件历史

最后编辑于 22 天前查看完整历史

题意 ​

思路 ​

代码 ​

贡献者 ​

文件历史 ​

题意

思路

代码

贡献者

文件历史