題目： UVa - 10306 - e-Coins

題目說明

Unfortunate狗的ACM園地: 10306 - e-Coins

解題思路

DP 的 Coin Change 問題，核心概念為枚舉每一個最後加入的面額。

參考解法

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int INF = (int)1e9;

int n, s;
pair<int, int> coin[41]; // Conventional, InfoTechnological
int dp[301][301];

void init()
{
    for (int i = 0; i <= 300; ++i) for (int j = 0; j <= 300; ++j) dp[i][j] = INF;
    dp[0][0] = 0;
}

void read()
{
    cin >> n >> s;
    s *= s;
    for (int i = 0; i < n; ++i) cin >> coin[i].first >> coin[i].second;
}

void CoinChange()
{
    for (int k = 0; k < n; ++k)
    {
        auto& [C, I] = coin[k];
        for (int i = C; i <= 300; ++i)
        {
            for (int j = I; j <= 300; ++j)
                dp[i][j] = min(dp[i - C][j - I] + 1, dp[i][j]);
        }
    }
}

void solve()
{
    int mn = INF;
    for (int i = 0; i <= 300; ++i) for (int j = 0; j <= 300; ++j)
        if (i * i + j * j == s) mn = min(dp[i][j], mn);

    if (mn == INF) { cout << "not possible\n"; return; }
    cout << mn << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        read();
        init();
        CoinChange();
        solve();
    }
}

參考資料

Unfortunate狗的ACM園地: 10306 - e-Coins