Untitled

 avatar
unknown
c_cpp
9 months ago
819 B
10
Indexable
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5;
long long arr[maxn], ans[maxn];

int main(){
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	
	for(int i = 1; i <= k && i < n; i++){
		ans[i] = abs(arr[0] - arr[i]);
		//cout << ans[i];
	}
	for(int i = 1; i < n - 1; i++){
		if(i + k < n){
			ans[i + k] = ans[i] + abs(arr[i] - arr[i + k]);
		}
		for(int j = 1; j < k && i + j < n; j++){
			ans[i + j] = min(ans[i + j], ans[i] + abs(arr[i] - arr[i + j]));
			//cout << "I " << i  << " ansi " << ans[i] << " i1 " << ans[i + j] << '\n';
		}
		
	}
/*	if(n > 2){
		ans[n - 1] = min(ans[n - 1], ans[n - 2] + abs(arr[n - 2] - arr[n - 1]));
	}
	if(n == 2){
		ans[n - 1] = ans[n - 2] + abs(arr[n - 2] - arr[n - 1]);
	} */
	
	cout << ans[n - 1];
}
Editor is loading...
Leave a Comment