00002 – Bajtolandzkie monety – programowanie dynamiczne
Treść zadania:
W Bajtolandi obowiązująca walutą są Bajtocoiny. Podczas kupowania pojawiał się problem z wydawaniem reszty. Z tego powodu przywódca Bajtolandi LordBajt zlecił napisanie programu obliczającego na ile sposób jest możliwe wydanie reszty o kwocie k mając do dyspozycji n typów monet.
Wejście:
W pierwszej linii podana jest kwota k jaką mamy wydać.
W drugiej linii podana jest liczba n oznaczająca liczbę typów monet jakimi dysponujemy, w kolejnej linii podanych jest n nominałów.
Wyjście:
Na wyjściu należy podać jedną liczbę całkowitą oznaczającą ilość sposób na jakie można wydać resztę. Jeżeli nie jest to możliwe wypisać 0.
Zakres danych:
0 ⩽ k ⩽ 10000
1 ⩽ n ⩽ 100
1 ⩽ a1, a2 … an ⩽ 10000
Wejście:
5
3
1 2 5
Wyjście:
4
Resztę możemy wydać na cztery sposoby:
1) 1 1 1 1 1
2) 1 1 1 2
3) 1 2 2
4) 5
Kod źródłowy w C++:
#include <iostream> using namespace std; int dp[10000][100]; int A[101]; int k, n; int solve(int a, int j) { if (a < 0 || j >= n || k == 0) { return 0; } else if (a == 0) { return 1; } else if (dp[a][j] > -1) { return dp[a][j]; } dp[a][j] = solve(a - A[j], j) + solve(a, j + 1); return dp[a][j]; } int main() { memset(dp, -1, sizeof(dp)); cin >> k >> n; for (int i = 0; i < n; i++) { cin >> A[i]; } cin.get(); cout << solve(k, 0); cin.get(); return 0; }