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
2. 用 10+3×1，找回 5+2×1（等價於先用 10，找 2 1，再用 3 1）；
3. 用 2×5， 找回 2×1
4. 用 5+3×1，不找零
5. 用 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>

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

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

signed main() { WA();
    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';
    }
}