問題は以下のように言い換えられます。

\(N\) 日のうち \(1\) 日以上のいくつかの日を休日にする。\(i\) 日目を休日にするコストは \(A_i\) である。 ただし隣り合う休日同士の間が \(2\) 日以上空いてはいけない。

最初の休日が \(S\) 日目、最後の休日が \(T\) 日目であるとしたとき \(T-S \geq K-1\) とするための最小コストを求めよ。

\(T-S\) は \(K-1\) または \(K\) の場合のみ考えればよく、その場合の最小コストは \(l=1,2,\dots,N-K\) についてそれぞれ以下の DP を考えたときの \(\mathrm{dp}_1[K]\) の最小値として求められます。 ただし \(\mathrm{INF}\) を十分大きな値（本問題の制約下では \(10^{18}\) など）、\(A_0=\mathrm{INF}\) とします。

• \(\mathrm{dp}_0[0]=0,\mathrm{dp}_1[0]=A_{l-1}\)．
• \(1\leq i\leq K\) に対して \(\mathrm{dp}_0[i]=\mathrm{dp}_1[i-1],\mathrm{dp}_1[i]=\min(\mathrm{dp}_0[i-1],\mathrm{dp}_1[i-1])+A_{l+i-1}\)．

しかし \(l\) ごとに上の DP を愚直に計算すると計算量が \(\Theta(KN)\) 時間となってしまいます。

写像 \(f_a\) を \(f_a(x,y)=(y,\min(x,y)+a)\) を満たすものとして定めると上の DP の遷移は

\[(\mathrm{dp}_0[i],\mathrm{dp}_1[i])=f_{A_{l+i-1}}(\mathrm{dp}_0[i-1],\mathrm{dp}_1[i-1])\]

として表現できるため、合成 \(f_{A_{l+K-1}}\circ\cdots\circ f_{A_{l+1}}\circ f_{A_{l}}\) を高速に求められればよいです。 \(f_{*}\) の合成は \((\min(x+a,y+b),\min(x+c,y+d))\) の形で表せるため、\(a,b,c,d\) の値を管理して区間積を求められるデータ構造を利用すれば計算することができます。

あるいは min-plus 代数の行列積

\[ \begin{pmatrix}\mathrm{dp}_0[K]\\\mathrm{dp}_1[K]\end{pmatrix} = \begin{pmatrix}\mathrm{INF}&0\\A_{l+K-1}&A_{l+K-1}\end{pmatrix} \cdots \begin{pmatrix}\mathrm{INF}&0\\A_l&A_l\end{pmatrix} \begin{pmatrix}\mathrm{dp}_0[0]\\\mathrm{dp}_1[0]\end{pmatrix} \]

として考えることもできます。

区間積の計算に Sliding Window Aggregation (SWAG) などを利用すれば \(O(N)\) 時間、セグメント木を利用すれば \(O(N\log N)\) 時間で解くことができます。

実装例(C++, SWAG) 実装例(C++, セグメント木)

また全体を長さ \(K\) ごとにブロックに分割し、ブロック内で prefix / suffix の累積積を計算して隣接するブロックの結果を組み合わせることでも \(O(N)\) 時間で解くことができます。

実装例(PyPy, ブロックに分割)