alan23273850 的刷題筆記
d397: 00147 - Dollars
Tags: coin-change
出處：https://zerojudge.tw/ShowProblem?problemid=d397
提交：https://zerojudge.tw/Submissions?problemid=d397&account=allllllan123456
問題：給定一個正整數 $n\in[1,30000]$，問你方程組 10000A + 5000B + 2000C + 1000D + 500E + 200F + 100G + 50H + 20I + 10J + 5K = $n$ 有多少組非負整數解。
解法：此乃 coin change 問題，可參閱本站對於該問題的解析。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
5 char ch; /* used for consuming . */
6 int x, y, price[] = {1,2,4,10,20,40,100,200,400,1000,2000};
7 long long DP[6001]={1}; // important initial condition
8 for (int i=0; i<sizeof(price) / sizeof(price[0]); i++)
9 for (int j=price[i]; j<=6000; j++)
10 DP[j] += DP[j-price[i]];
11 while (cin >> x >> ch >> y && (x||y))
12 cout << setw(3) << x << '.' << setw(2) << setfill('0') << y,
13 cout << setw(17) << setfill(' ') << DP[(100*x+y) / 5] << '\n';
14 return 0;
15}