fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[100000];
  5. int rec(int arr[],int i,int n,int kk){
  6. if(i==n-1)
  7. return 0;
  8. if(i>n-1)
  9. return INT_MAX;
  10. if(dp[i]!=-1)
  11. return dp[i];
  12.  
  13. // int f=INT_MAX;
  14. // if(i+1<n)
  15. // f=rec(arr,i+1,n)+abs(arr[i]-arr[i+1]);
  16. // int k=INT_MAX;
  17. // if(i+2<n)
  18. // k=rec(arr,i+2,n)+abs(arr[i]-arr[i+2]);
  19. int cost=INT_MAX;
  20. for(int l=1;l<=kk;l++){
  21. if(i+l<n)
  22. cost=min(cost,rec(arr,i+l,n,kk)+abs(arr[i]-arr[i+l]));
  23. }
  24.  
  25.  
  26. return dp[i]=cost;
  27. }
  28. int main() {
  29. memset(dp,-1,sizeof(dp));
  30. int n,k;
  31. cin>>n>>k;
  32. int arr[n];
  33. for(int i=0;i<n;i++){
  34. cin>>arr[i];
  35. }
  36. cout<<rec(arr,0,n,k)<<endl;
  37. return 0;
  38. }
Success #stdin #stdout 0.01s 5360KB
stdin
5 3
10 30 40 50 20
stdout
30