比赛 2022级数学专题练习赛10 评测结果 AAAAAAAAAA
题目名称 硬币购物 最终得分 100
用户昵称 zxhhh 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-04-12 19:46:39
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;
const int S = 1e5+5;
typedef long long ll;
int c[5], tot, d[5], s;
ll dp[S];

int main () {
    freopen("coin.in", "r", stdin);
    freopen("coin.out", "w", stdout);
    for (int i = 1;i <= 4;i++) cin >> c[i];
    cin >> tot;
    dp[0] = 1;
    for (int i = 1;i <= 4;i++) {
        for (int j = c[i];j <= 1e5;j++) dp[j] += dp[j-c[i]];
    }
    while (tot--) {
        for (int i = 1;i <= 4;i++) cin >> d[i]; cin >> s;
        ll ans = 0;
        for (int i = 0;i < (1<<4);i++) {
            int op = 1, j = i; ll k = 0;
            for (int z = 0;z < 4;z++, j >>= 1) {
                if (j&1) {
                    op ^= 1;
                    k += (d[z+1]+1)*c[z+1];
                }
            }
            if (k > s) continue;
            if (op) ans += dp[s-k];
            else ans -= dp[s-k]; 
        }
        cout << ans << endl;
    }
    return 0;
}