題目： UVa - 165 - Stamps

題目說明

給兩個整數 h、k，分別代表最多能貼 h 張郵票，及最多能使用 k 種面額的郵票，求最多能組出從 1 開始數到多少的價格。

如 1 3 -> 7，表示使用面額 1 和 3 的郵票，可以組出 1 ~ 7 這 7 種價格。

Input： 每行兩個整數，分別代表 h、k，若皆為 0 表示結束。

Output： 輸出選取的 k 種面額，及最多能組出從 1 開始數到多少的價格。

解題思路

由於數據量較少，所以暴力法模擬即可。

先模擬出 k 個面額，stamp 儲存目前模擬的面額，maxVal[i] = d 表示 i + 1 張郵票能組出 1 ~ d 的價格，第一個面額一定是 1 也就是 stamp[0] = 1，而 maxVal[0] 一定是 h，由於我們的目標是組出 1 ~ 多少的價格，因此後面的金額範圍為 stamp[i - 1] + 1 ~ maxVal[i - 1] + 1，依此想法做 DFS 模擬出 k 個面額，而 maxVal 也是使用 DFS 取得。

最後根據題目要求輸出答案即可。

參考解法

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
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fFRd4x

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

int h, k;
int mx;
int stamp[10] = { 1 };
int ans[10];
int maxVal[10];
bool check[180];

void init()
{
    mx = 0;
    maxVal[0] = h;
}

int getVal()
{
    int i = 0, cnt = 0;
    while (check[++i]) ++cnt;
    return cnt;
}

void dfs(int n, int idx, int sum)
{
    check[sum] = true;
    if (n == h) return; // 若已選了 h 張郵票
    for (int i = 0; i <= idx; ++i) dfs(n + 1, idx, sum + stamp[i]);
}

// 模擬最多 k 種面額的郵票組合
void execute(int idx = 1)
{
    if (idx == k)
    {
        if (maxVal[idx - 1] > mx)
        {
            mx = maxVal[idx - 1];
            memcpy(ans, stamp, sizeof(stamp));
        }
        return;
    }

    for (int i = stamp[idx - 1] + 1; i <= maxVal[idx - 1] + 1; ++i)
    {
        stamp[idx] = i;
        memset(check, 0, sizeof(check));
        dfs(0, idx, 0);
        maxVal[idx] = getVal();
        execute(idx + 1);
    }
}

void solve()
{
    for (int i = 0; i < k; ++i) cout << setw(3) << ans[i];
    cout << " ->" << setw(3) << mx << '\n';
}

int main()
{
    while (cin >> h >> k && (h || k))
    {
        init();
        execute();
        solve();
    }
}

參考資料

uva 165 Stamps_@fei-CSDN博客