Slope Trickと呼ばれるテクニックに落とし込む方法です。

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

関数 \(f(x)\) が最初 \(f(x) = 0\) で初期化されている。\(i = 1,2,...,N\) について、\(f(x)\) を \(f(x) + \max (0, x - D_i) + \max (0, D_i - K + 1 - x)\) で置き換える。すべての操作が終わった後の \(f(x)\) の最小値を求めよ。

（直感的には \(f(x)\) は選ぶ区間の始点を \(x\) としたときの不満度を表していると見ることができます。）

これは、区分線形凸関数の加算と最小値取得ができるデータ構造があれば良く、まさにそのようなクエリを処理するテクニックが Slope Trick という名称で知られています。詳細については以下の記事を参照ください。

maspyさんの解説記事

また、もう少し考察を進めると、結局のところ区間の始点として採用するべき値は \((D_1, D_1 - K +1, D_2, D_2 - K + 1, \dots, D_N - K + 1)\) の \(2N\) 個の値をソートしたときに \(N\) 番目の値が最適であることもわかるため、そのような方法でも解くことができます。

実装例（Nim）