Advertisement
Guest User

Untitled

a guest
Oct 19th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5.  
  6. int main() {
  7.     int n;
  8.     cin >> n;
  9.     vector<int> a(n);
  10.     for (auto& i : a) cin >> i;
  11.     int k;
  12.     cin >> k;
  13.     vector<int> dp(n + 1);
  14.     dp[0] = 0;
  15.     for (int m = 1; m <= n; ++m) {
  16.         dp[m] = INF;
  17.         for (int i = 0; i < k; ++i) {
  18.             if (m >= a[i] && dp[m - a[i]] + 1 < dp[m]) {
  19.                 dp[m] = dp[m - a[i]] + 1;
  20.             }
  21.         }
  22.     }
  23.     if (dp[n] == INF) {
  24.         cout << -1;
  25.     } else {
  26.         while (n > 0) {
  27.             for (int i = 0; i < k; ++i) {
  28.                 if (dp[n - a[i]] == dp[n] - 1) {
  29.                     cout << a[i] << " ";
  30.                     n -= a[i];
  31.                     break;
  32.                 }
  33.             }
  34.         }
  35.     }
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement