Warp Star

以下のような動的計画法を考えてみましょう。

$dp[i] :$ 番号 $i$ の星にたどり着くために必要なコストの最小値

dp テーブルを十分大きな値で初期化しておくと、遷移は以下のようになります。

$dp[1] = 0$
$dp[i] = \min(dp[l], dp[l + 1], ..., dp[i - 1]) + A[i] \: (l = \max(1, i - k))$

よって、区間の最小値を Segment Tree や Sparse Table などで求めることによってこの問題を十分高速に解くことができます。