# 題目: UVa 165 - Stamps
# 題目說明
有 k 種面額郵票,每張明信片上最多能貼 h 張郵票n(h, k) 代表從 k 種面額中選擇至多 h 張郵票,使得可以組成面額為 1 2 3 4 ... n 的連續整數明信片
求 n 的最大值,及是哪 k 種面額的郵票
例如:h = 3 及 k = 2
則面額 1 與 3 可以組成連續最大 7 種面額的明信片
( 1 、 1+1 、 3 、 3+1 、 3+1+1 、 3+3 、 3+3+1 )
當面額為 1 與 2 或 1 與 4 時,只能組出最大 6 種
不論 h 與 k 是多少,一定包刮面額為 1 的郵票,不然就無法組成面額為 1 的明信片
INPUT:
每筆測資輸入兩個整數 h 與 k
當 h 與 k 為 0 時,結束程式
OUTPUT:
輸出能組成最大 n 面額的郵票,與 n 的值
# 解題方法
以下的寫法是使用雙層 dfs 去遍歷所有可能,若使用 dfs + dp 的話能增加效率
stamp 儲存目前的郵票組合,第一層 dfs search 則為遍歷所有郵票組合maxstamp[i] 儲存第 i 張郵票能從 1 開始數到得最大值
對於 stamp[i + 1] 的範圍為 stamp[i] + 1 到 maxstamp[i] + 1
( stamp[0] 一定為 1 、 maxstamp[0] 一定為 h )
第二層 dfs 為固定郵票組合,遍歷所有可能數量的郵票組合
例如 h = 3 及 k = 2 時
第一層 dfs 會找出 1 2 、 1 3 、 1 4 3 種組合
固定 1 2 時,會找出 1 、 2 、 1+2 、 2+2 、 1+2+2 、 2+2+2 等 6 種組合
以此類推...
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <iomanip> | |
#include <map> | |
using namespace std; | |
int h, k, maxval; | |
map<int, int> stamp; | |
map<int, int> maxstamp; | |
map<int, int> ans; | |
vector<bool> check; | |
void dfs(int cur, int index, int sum) | |
{ | |
if (cur == h) | |
{ | |
check[sum] = true; | |
return; | |
} | |
check[sum] = true; | |
for (int i = 0; i <= index; ++i) dfs(cur + 1, index, sum + stamp[i]); | |
} | |
void search(int index) | |
{ | |
if (index == k) | |
{ | |
if (maxstamp[index - 1] > maxval) | |
{ | |
maxval = maxstamp[index - 1]; | |
ans = stamp; | |
} | |
return; | |
} | |
for (int i = stamp[index - 1] + 1; i <= maxstamp[index - 1] + 1; ++i) | |
{ | |
check.assign(200, false); | |
stamp[index] = i; | |
dfs(0, index, 0); | |
int j = 0, num = 0; | |
while (check[++j]) ++num; | |
maxstamp[index] = num; | |
search(index + 1); | |
} | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
while (cin >> h >> k, h && k) | |
{ | |
stamp.clear(); | |
maxstamp.clear(); | |
maxval = 0; | |
stamp[0] = 1; | |
maxstamp[0] = h; | |
search(1); | |
for (auto& [key, val] : ans) cout << setw(3) << val; | |
cout << " ->" << setw(3) << maxval << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://blog.enmingw32.dev/2018/09/15/UVa-165-Stamps/
https://blog.csdn.net/shuangde800/article/details/7755452