Untitled
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