This problem consists to minimise the answer at each step. Here I'm explaning my C++ code on the following example:
6
30 10 60 10 60 50
ret : [Ø, 20, 30, 20, 30, 40]
ret[0] = Ø
ret[1] = ret[0] + abs(v[0] - v[1])
ret[2] = ret[1] + max( abs(v[0] - v[2]), abs(v[1] - v[2]) )
(In this case, it's ret[1])
.......
C++ code
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,K;
cin >> n >> K;
vector<int> v(n+3),ret(n+3,INT_MAX);
for (int i=0; i<n; ++i) cin >> v[i];
ret[0]=0;
for (int i=0; i<n; ++i){
for (int k=1; k<=K; ++k) ret[i+k] = min(ret[i+k],abs(v[i]-v[i+k])+ret[i]);
}
cout << ret[n-1];
return 0;
}
No comments:
Post a Comment