Submission #67455835

---

Source Code Expand

// 綺麗に解きなおし

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, k;
  cin >> n >> k;

  vector<int> h(n);
  for (int i=0; i<n; i++) {
    cin >> h.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  //////////////////// 処理 ////////////////////

  // DP用の配列
  // cost.at(i)はi番目（0始まりで）の足場への最小コスト
  // ありえる最大値より大きい値で埋めておく
  vector<int> cost(n,2e9);

  // 最初の1つは特殊処理なのでループ外で埋める
  cost.at(0) = 0;

  // 2つめ以降をもらうDPで求める
  for (int i=1; i<n; i++) {

    // その足場へ移動できる元の足場全てに対してループ
    for (int j=max(0,i-k); j<i; j++) {

      // j番目（0始まりで）からジャンプしてくる場合のコスト// 今のデータより小さかったら更新
      cost.at(i) = min(cost.at(i),cost.at(j)+abs(h.at(i)-h.at(j)));

    }

  }

  // 最後の足場の最小コストが答え
  result = cost.at(n-1);

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result