alan23273850 的刷題筆記
d289: 多元一次方程式
Tags: coin-change
出處：https://zerojudge.tw/ShowProblem?problemid=d289
提交：https://zerojudge.tw/Submissions?problemid=d289&account=allllllan123456
問題：給定一個正整數 $I\in[1,8000]$，問你方程組 1A + 13B + 33C + 43D + 139E + 169F + 1309G + 2597H = $I$ 有多少組非負整數解。
解法：此乃 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 price[] = {1,13,33,43,139,169,1309,2597};
6 int n, DP[8001]={1}; // important initial condition
7 for (int i=0; i<8; i++)
8 for (int j=price[i]; j<=8000; j++)
9 DP[j] += DP[j-price[i]];
10 while (cin >> n) cout << DP[n] << '\n';
11 return 0;
12}