洛谷1450：硬币购物

洛谷1450：硬币购物

题目描述：

• 有四种面值的硬币，面值分别为\(c1,c2,c3,c4\)。
• 某人去商店买东西，一共去了\(T\)次，每次带\(d_i\)枚\(c_i\)硬币，买价值为\(s_i\)的东西，问每次有多少种付款方法。

数据范围：

• \(d_i,s_i \leq 1e5\)
• \(tot\leq 1000\)

思路：

• 背包+容斥
• 对于每一次询问都做一次多重背包，肯定会超时。
• 暂且先考虑如果每种硬币可以无限次的使用会发生什么情况。
• 那就是完全背包，可以用\(f(i)\)来表示每种硬币选择任意多次的方案数，有转移方程\(f(j)=f(j-c(i))\)。
• 先来考虑只有一种硬币的情况。
• 这里的方案数可能是超过了\(d\)个的，也就是说结果可能是存在有使用了\(d+1,d+2,...\)种方案的情况，所以我们需要把他减去。
• 这里要怎么做呢，先举个例子，比如说我现在有两个区间\([2,+\infin]\)和\([3,+\infin]\)。我想要得到\([2,3]\)区间我只需要将这两个区间相减即可。
• 那么我们只需要考虑选则任意数量的方案，减去选则\(d+1\)个硬币的方案。
• 那么可以知道\(ans = f(s)-(f(s)-c*(d+1))\)。这样就是选择无限的减去选则\(d+1\)的。
• 对于多种硬币，就有\(ans=f(s)-\sum_{i=1}^{4}f(s-c_i*(d_i+1))\)。
• 但是这个式子只是意会用的，他是不能直接累加的，因为可能种类\(1\)的硬币超出限制，种类\(2\)的硬币超出限制，而直接累加会导致冗余情况。
• 所以需要容斥定理，当然这里只有四种硬币，所以可以直接枚举，但是用位运算枚举会方便很多。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int c[5], d[5], s, T;
ll f[maxn], ans;

int main()
{
    for(int i = 1; i <= 4; i++) scanf("%d", &c[i]);
    f[0] = 1;
    for(int i = 1; i <= 4; i++)
        for(int j = c[i]; j <= maxn-5; j++)
            f[j] += f[j-c[i]];

    scanf("%d", &T);
    while(T--)
    {
        ll ans = 0;
        for(int i = 1; i <= 4; i++)
            scanf("%d", &d[i]);
        scanf("%d", &s);
        ans = f[s];
        for(int i = 1; i < (1<<4); i++)
        {
            ll tmp = 0, num = 0;
            for(int j = 1; j <= 4; j++)
            {
                if((1<<(j-1))&i)
                {
                    num++;
                    tmp += (d[j]+1) * c[j];
                }
            }
            if(tmp > s) continue;
            if(num % 2 == 0) ans += f[s-tmp];
            else ans -= f[s-tmp];
        }
        cout << ans << endl;
    }

    return 0;
}

洛谷1450：硬币购物

原文：https://www.cnblogs.com/zxytxdy/p/12063893.html