10626 Buying Coke

題目連結

題目敘述

我經常在公司裡的自動販賣機買可樂
通常我一次會買好幾瓶，因為我的同事們也喜歡喝可樂
自動販賣機上的一瓶可樂售價為 8 瑞典克朗
且機器只接受面額為 1、5 和 10 的硬幣
當我按下可樂的按鈕（在投入足夠的錢之後）時
我會先得到一瓶可樂，再拿到零錢（如果有的話）
零錢總是以最少硬幣數量找回（由於硬幣面額固定，此方式下找零方式唯一）
這個過程會重複，直到我買完所有想要的可樂
請注意，我可以將拿到的零錢重投入機器以購買後續的可樂

現在，給定我想買的可樂數量，以及我手上各面額硬幣的數量
問我至少需要投入多少硬幣？假設販賣機永遠不會缺硬幣
而且我手上的錢總額足以買完所有的可樂

輸入格式

• 第一行包含測試資料組數目 T（T ≤ 50）。
• 接下來每組資料各佔一行，包含四個整數：
  • C：想買的可樂數量（1 ≤ C ≤ 150）
  • n₁：1 元硬幣的數量（0 ≤ n₁ ≤ 500）
  • n₅：5 元硬幣的數量（0 ≤ n₅ ≤ 100）
  • n₁₀：10 元硬幣的數量（0 ≤ n₁₀ ≤ 50）

輸出格式

對於每組測試資料，在一行上輸出一個整數：投入機器的最少硬幣數量。

解題思路

此題有兩種解法分為

• 貪心（較快）
• 遞迴枚舉 + 記憶化搜索（較慢）

1. 貪心

2. 遞迴枚舉 + 記憶化搜索

狀態以 a, b, c 表示當前手上有 a 枚 1 元、b 枚 5 元、c 枚 10 元
分別對五種條件進行遞迴枚舉

1. 用 10 元，找回 2×1，成本 1
2. 用 10+3×1，找回 5+2×1（等價於先用 10，找 2 1，再用 3 1），成本 4
3. 用 2×5，找回 2×1，成本 2
4. 用 5+3×1，不找零，成本 4
5. 用 8×1，不找零，成本 8

結束條件為 剩餘硬幣的金額 等於 初始金額 - 購買所有可樂所需的金額 並搭配記憶化搜索以避免重複計算

程式碼

1. 貪心

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

signed main() { WA();
    int t; cin >> t;
    while (t--) {
        int n, c1, c5, c10, ans = 0; cin >> n >> c1 >> c5 >> c10;
        if (c10 >= n) cout << c10;
        else {
            n -= c10;
            if (c5 >= n*2) cout << c10 + n*2;
            else if (c5 >= n) cout << c10 + 6*n - 2*c5;
            else if (c10 >= n - c5) cout << c10 + 2*n - 2*c5;
            else cout << 8*n + 4*c5;
        }
        cout << '\n';
    }
}

2. 遞迴枚舉 + 記憶化搜索

#include <bits/stdc++.h>
using namespace std;

int k, dp[800][300][100];

int dfs(int a, int b, int c) {
    if (k == a + b*5 + c*10) return 0;
    int &N = dp[a][b][c];
    if (N) return k;
    N = INF;
    if (c > 0) N = min(N, dfs(a+2, b, c-1) + 1);
    if (c > 0 && a >= 3) N = min(N, dfs(a-3, b+1, c-1) + 4);
    if (b >= 2) N = min(N, dfs(a+2, b-2, c) + 2);
    if (b > 0 && a >= 3) N = min(N, dfs(a-3, b-1, c) + 4);
    if (a >= 8) N = min(N, dfs(a-8, b, c) + 8);
    return N;
}

int main() {
    int t, n, a, b, c;
    cin >> t;
    while (t--) {
        cin >> n >> a >> b >> c;
        k = a + b*5 + c*10 - n*8;
        memset(dp, 0, sizeof(dp));
        cout << dfs(a, b, c) << '\n';
    }
}