P1450 [HAOI2008] 硬币购物

2025-05-27

有点难吧，看题解看了会没看懂。但也不是很难看懂。

其实我们就是先把所有硬币都不设置限制的答案求出来，然后再把超出限制的方案给减掉。

那么超出限制的方案就是 1种硬币超出 - 2种硬币超出 + 3种硬币超出 - 4种硬币超出 的方案数。

那么我们只需要枚举子集，对于每一种硬币, \(dp_{cur - c_{i}(d_{i}+1)}\) 就是这种硬币超出了限制的方案数，因为这个肯定是使用次数大于 \(d_i\) 了，我们并不需要去关心它具体使用了多少次，也不用去在意其它硬币使用的情况。

多种硬币超出限制的情况也是同理的。

// #define YUANSHEN
#if defined(YUANSHEN)
#include "C:/codes/cp_code/template/debug.hpp"
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) 42
#endif

#define rep(N) for(int i = 1; i <= N; i++)

template <typename T1, typename T2>
void cmin(T1& x, const T2& y)
{
    x = x < y ? x : y;
}
template <typename T1, typename T2>
void cmax(T1& x, const T2& y)
{
    x = x > y ? x : y;
}
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vc = vector<T>;

#define fixset(x) fixed << setprecision(x)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ALL(x) (x).begin() + 1, (x).end()
constexpr int INF = 1000000000;
constexpr ll LNF = 1000000000000000000LL;

// Date: 2025-05-27
// Time: 15:07:58
constexpr int N = int(1e5);
ll dp[N + 1], c[5], d[5];

void ChatGptDeepSeek()
{
    int q;
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> q;
    dp[0] = 1;
    for(int i = 1; i <= 4; i++){
        for(int j = c[i]; j <= N; j++)
            dp[j] += dp[j - c[i]];
    }
    while(q--){
        for(int i = 1; i <= 4; i++)
            cin >> d[i];
        int s;
        cin >> s;
        ll ans = dp[s];
        for(int mask = 1; mask <= 15; mask++){
            ll x = 0;
            for(int j = 0; j < 4; j++){
                if(mask >> j & 1) x += c[j + 1] * (d[j + 1] + 1);
            }
            if(x > s) continue;
            if(__builtin_popcount(mask) & 1) ans -= dp[s - x];
            else ans += dp[s - x];
        }
        cout << ans << '\n';
    }
}

int main()
{
#ifndef YUANSHEN
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#endif
    int T = 1;
    // cin >> T;
    while (T--)
        ChatGptDeepSeek();
    return 0;
}