Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int maxn = 1e5 + 10;
- const int INF = 2e9 + 5;
- int array[100000];
- int dp[1000000];
- int k,n;
- int rec(int a)
- {
- if (a==n-1)
- {
- return 0;
- }
- if (dp[a]!=-1)
- {
- return dp[a];
- }
- int y=1e9;
- for (int j=1;j<=k;j++)
- { if (a+j<n)
- { y=min(y, abs(array[a]-array[a+j]) + rec (a+j) );
- } }
- dp[a]=y;
- return y;
- }
- int main()
- {
- cin>>n>>k;
- for (int i=0;i<n;i++)
- {
- cin>>array[i];
- }
- for (int i=0;i<1e6;i++)
- {
- dp[i]=-1;
- }
- cout<<rec(0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment