Advertisement
lodha1503

Untitled

Aug 25th, 2023
683
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define MOD1 1000000007
  6. #define MOD2 998244353
  7. #define NO cout << "NO" << endl
  8. #define YES cout << "YES" << endl
  9. ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  10. ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
  11. ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
  12. ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
  13. ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
  14. ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}
  15. void print(vector<int> &ans){for(auto x: ans) cout<<x<<" "; cout<<endl;}
  16.  
  17. // ========================================================================================================================================================================================================
  18.  
  19.  
  20. int memo(int n,int k,vector<int> &heights,vector<int> &dp,int ind)
  21. {
  22.     if(ind==0)
  23.         return 0;
  24.     if(dp[ind]!=-1)
  25.         return dp[ind];
  26.     int mini=INT_MAX;
  27.     for(int i=1;i<=k;i++)
  28.     {
  29.         if(ind-i>=0)
  30.             mini=min(mini,memo(n,k,heights,dp,ind-i)+abs(heights[ind-i]-heights[ind]));
  31.            
  32.     }
  33.    
  34.     dp[ind]=mini;
  35.    
  36.     return dp[ind];
  37. }
  38.  
  39.  
  40. int tabularization(int n,int k,vector<int> &heights,vector<int> &dp)
  41. {
  42.     dp[0]=0;
  43.     dp[1]=min(heights[1],abs(heights[1]-heights[0]));
  44.  
  45.     for(int ind=2;ind<n;ind++)
  46.     {
  47.         int mini=INT_MAX;
  48.         for(int i=1;i<=k;i++)
  49.         {
  50.             if(ind-i>=0)
  51.                 mini=min(mini,dp[ind-i]+abs(heights[ind-i]-heights[ind]));
  52.         }
  53.         dp[ind]=mini;
  54.     }
  55.     return dp[n-1];
  56. }
  57. void solve()
  58. {
  59.    
  60.     int n,k;
  61.     cin>>n>>k;
  62.     vector<int> heights;
  63.     vector<int> dp(n,-1);
  64.    
  65.     for(int i=0;i<n;i++)
  66.     {
  67.         int h;cin>>h;
  68.         heights.pb(h);
  69.     }
  70.    
  71.     // cout<<memo(n,k,heights,dp,n-1)<<endl;
  72.     cout<<tabularization(n,k,heights,dp)<<endl;
  73.    
  74. }
  75.  
  76.  
  77. int main()
  78. {
  79.    
  80.   solve();
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement