以下の動的計画法ができれば、この問題に正解できます。

• \(dp[i] = \{\) 石 \(i\) に到達するための最小コスト \(\}\)

この動的計画法は以下のようにして実現できます。

• \(dp[1] = A_1\) と初期化する。
• \(i=2,3,\dots,N\) について、以下を繰り返す。
  • \(dp[i]\) を、 \(dp[i-K],dp[i-K+1],\dots,dp[i-1]\) の最小値に \(A_i\) を加えたものとする。 (但し、範囲外参照は適切に対処する。)
• 最終的な答えは \(dp[N]\) である。

\(dp\) の要素を複数参照した結果で \(dp\) の一点の値を求めることから、これは 貰うDP、集めるDP とも呼ばれます。

このまま実装すると時間計算量が \(O(NK)\) となり TLE してしまいますが、「 \(dp[i-K],dp[i-K+1],\dots,dp[i-1]\) の最小値を求める」という操作は segment tree を使って高速化できます。

時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;
using ll=long long;

ll op(ll x,ll y){return min(x,y);}
ll e(){return 4e18;}

int main(){
  ll n,k;
  cin >> n >> k;
  vector<ll> a(n);
  for(auto &nx : a){cin >> nx;}
  segtree<ll,op,e> seg(n);
  seg.set(0,a[0]);
  for(ll i=1;i<n;i++){
    seg.set(i,seg.prod(max(0ll,i-k),i)+a[i]);
  }
  cout << seg.get(n-1) << "\n";
  return 0;
}