Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define pb push_back
- #define MOD1 1000000007
- #define MOD2 998244353
- #define NO cout << "NO" << endl
- #define YES cout << "YES" << endl
- 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;}
- ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
- ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
- ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
- ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
- 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;}
- void print(vector<int> &ans){for(auto x: ans) cout<<x<<" "; cout<<endl;}
- // ========================================================================================================================================================================================================
- int memo(int n,int k,vector<int> &heights,vector<int> &dp,int ind)
- {
- if(ind==0)
- return 0;
- if(dp[ind]!=-1)
- return dp[ind];
- int mini=INT_MAX;
- for(int i=1;i<=k;i++)
- {
- if(ind-i>=0)
- mini=min(mini,memo(n,k,heights,dp,ind-i)+abs(heights[ind-i]-heights[ind]));
- }
- dp[ind]=mini;
- return dp[ind];
- }
- int tabularization(int n,int k,vector<int> &heights,vector<int> &dp)
- {
- dp[0]=0;
- dp[1]=min(heights[1],abs(heights[1]-heights[0]));
- for(int ind=2;ind<n;ind++)
- {
- int mini=INT_MAX;
- for(int i=1;i<=k;i++)
- {
- if(ind-i>=0)
- mini=min(mini,dp[ind-i]+abs(heights[ind-i]-heights[ind]));
- }
- dp[ind]=mini;
- }
- return dp[n-1];
- }
- void solve()
- {
- int n,k;
- cin>>n>>k;
- vector<int> heights;
- vector<int> dp(n,-1);
- for(int i=0;i<n;i++)
- {
- int h;cin>>h;
- heights.pb(h);
- }
- // cout<<memo(n,k,heights,dp,n-1)<<endl;
- cout<<tabularization(n,k,heights,dp)<<endl;
- }
- int main()
- {
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement