DPまとめコンテスト B - Frog 2

B - Frog 2

概要

数列がある。この数列を0とばし、1とばし、…　、とばしのいずれかで進む。
からに進むとき、コストがかかる。
からに進むときのコストの総和の最小値を求めよ。

制約

方針

A問題同様、コストを配列にする。
A問題は1個前からの移動、2個前からの移動とのminをとっていたが、
この問題では1個前からの移動、２個前からの移動、…　、K個前からの移動とのminをとればよい。

解答

Submission #3939065 - Educational DP Contest / DP まとめコンテスト

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, k;
	cin >> n >> k;
 
	ll h[n];
	rep(i, n) cin >> h[i];
 
	ll INF = 1e13;
	ll c[n];
	rep(i, n) c[i] = INF;
	c[0] = 0;
 
	for(int i = 1; i < n; i++){
		for(int j = max(i-k, 0); j < i; j++){
			c[i] = min(c[i], c[j] + abs(h[j] - h[i]));
		}
	}
 
	cout << c[n-1] << endl;
}