Frog 1

Problem Statement : https://atcoder.jp/contests/dp/tasks/dp_a

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;

}