alan23273850 的刷題筆記
d133: 00357 - Let Me Count The Ways
Tags: coin-change
出處：https://zerojudge.tw/ShowProblem?problemid=d133
提交：https://zerojudge.tw/Submissions?problemid=d133&account=allllllan123456
問題：給定一個非負整數 $n\in[0,30000]$，問你方程組 1A + 5B + 10C + 25D + 50E = $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 int n, price[] = {1,5,10,25,50};
6 long long DP[30001]={1}; // important initial condition
7 for (int i=0; i<sizeof(price) / sizeof(price[0]); i++)
8 for (int j=price[i]; j<=30000; j++)
9 DP[j] += DP[j-price[i]];
10 while (cin >> n)
11 if (DP[n] == 1) cout << "There is only 1 way to produce " << n << " cents change.\n";
12 else cout << "There are " << DP[n] << " ways to produce " << n << " cents change.\n";
13 return 0;
14}