Advertisement
Korotkodul

dp

Sep 15th, 2022 (edited)
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17.     for (auto x: v) cout<<x<<' ';
  18.     cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22.     for (auto x: v) cout<<x<<' ';
  23.     cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28.     for (auto x: v) cv(x);
  29.     cout<<"\n";
  30. }
  31.  
  32. void cvb(vector <bool> v){
  33.     for (bool x: v) cout<<x<<' ';
  34.     cout<<"\n";
  35. }
  36.  
  37. void cvs(vector <string>  v){
  38.     for (auto a: v){
  39.         cout<<a<<"\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a){
  44.     for (auto p: a){
  45.         cout<<p.first<<' '<<p.second<<"\n";
  46.     }
  47.     cout<<"\n";
  48. }
  49.  
  50.  
  51.  
  52. int main()
  53. {
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0);
  56.     cout.tie(0);
  57.     int n,m; cin>>n>>m;
  58.     vector <int> a(n+1); for (int i = 1; i <= n; ++i) cin>>a[i];
  59.     vector <vector<int>> dp(m+1, vector <int> (n+1, -1));
  60.     for (int j = 0; j <= n; ++j) dp[0][j] = 0;
  61.  
  62.     for (int i = 1; i <= m; ++i){
  63.         for (int j = 1; j <= n; ++j){
  64.             if (dp[i][j-1] != -1){
  65.                 dp[i][j] = dp[i][j-1];
  66.             }
  67.             if (i - a[j] >= 0 && dp[i - a[j]][j - 1] != -1){
  68.                 if (dp[i][j] == -1){
  69.                     dp[i][j] = dp[i - a[j]][j - 1] + 1;
  70.                 }
  71.                 else{
  72.                     dp[i][j] = min(dp[i][j - 1], dp[i - a[j]][j - 1] + 1);
  73.                 }
  74.             }
  75.         }
  76.     }
  77.     if (dp[m][n] == -1){
  78.         cout<<0;
  79.         exit(0);
  80.     }
  81.     cout<<dp[m][n];
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement