alan23273850 的刷題筆記
d119: 有獎徵答：換零錢
Tags: coin-change
出處：https://zerojudge.tw/ShowProblem?problemid=d119
提交：https://zerojudge.tw/Submissions?problemid=d119&account=allllllan123456
問題：給定一堆總和不超過 50000 的正整數集合 S，問你方程組 1A + 5B + 10C + 20D + 50E + 100F + 200G + 500H + 1000I + 2000J = sum(S) 有多少組非負整數解。輸出的答案還要再扣掉一。
解法：此乃 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 t, sum, price[] = {1,5,10,20,50,100,200,500,1000,2000};
6 long long DP[50001]={1}; // important initial condition
7 for (int i=0; i<sizeof(price) / sizeof(price[0]); i++)
8 for (int j=price[i]; j<=50000; j++)
9 DP[j] += DP[j-price[i]];
10 while (scanf("%d", &sum) && sum) {
11 while (getchar() != '\n') scanf("%d", &t), sum += t;
12 cout << DP[sum] - 1 << '\n';
13 }
14 return 0;
15}