题意

给出10张硬币,问如何凑出P¥且数量最多,无方案输出-1

思路

如果面值连续,后一个是前一个的倍数,从大往小凑,用小因子去凑更多的硬币, 但是本题存在$20,200$特殊处理这两种情况100¥折成2 * 50,500拆成5 * 100,或200* 2+100

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 22;
typedef long long ll;
#define cmax(a, b)a=max(a,b)
#define cmin(a, b)a=min(a,b)

int a[maxn];
int b[maxn] = {0, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};
ll sum[maxn];
int ans;

void solve(ll p, int idx, int cnt) {
    if (p < 0) return;
    if (!idx && !p) { // finishit
        cmax(ans, cnt);
        return;
    }
    ll rp = max(0ll, p - sum[idx - 1]);//后面的凑完了,还要凑多少钱
    ll nc = rp / b[idx];//当前的面值能凑几张
    if (rp % b[idx]) nc++;
    if (nc <= a[idx]) solve(p - nc * b[idx], idx - 1, cnt + nc);//考虑np奇偶性
    if (nc + 1 <= a[idx]) solve(p - (nc + 1) * b[idx], idx - 1, cnt + nc + 1);
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int p; scanf("%d", &p);
        for (int i = 1; i <= 10; i++) {
            scanf("%d", &a[i]);
            sum[i] = sum[i - 1] + (ll) b[i] * a[i];
        }
        ans = -1;
        solve(p, 10, 0);
        printf("%d\n", ans);
    }
}

星星 当夜色降临 我站在台阶上倾听; 星星蜂拥在花园里 而我站在黑暗中。 听,一颗星星落地作响! 你别赤脚在这草地上散步, 我的花园到处是星星的碎片