この問題は、答えが \(i\) に対して上に凸であることが重要です。ただし、この解説を書いている現在は公式解説には凸であることの証明が書かれておりません。

その証明を簡単にします。

示したいのは以下です。

補題

\(f(i)\) を最適解とします。このとき、整数 \(1\leq i<\lfloor\frac{N}{K}\rfloor\) に対して、\(f(i) + f(i + 2)\leq 2f(i + 1)\) が成り立つ。

\(f(i)\) の最適解を満たすタイルの置き方の左端の index を昇順に並べた列を \(g(i) = (a_{i, 1}, a_{i, 2}, \cdots , a_{i, i})\) とします。このとき、\(a_{i, j} + K \leq a_{i, j + 1}\) が成り立ちます。

\(2\) つの数列 \(g(i), g(i + 2)\) を結合して昇順ソートした列を \(A = (A_{1}, A_{2}, \dots A_{2i + 2})\) とします。

数列 \(B, C\) を \(B = (A_{1}, A_{3}, \cdots A_{2i + 1})\) と \(C = (A_{2}, A_{4}, \cdots A_{2i + 2})\) としたとき、\(B, C\) はいずれも昇順ソートされており、隣接要素が \(K\) 以上離れています。

隣接要素が \(K\) 以上離れていることは、\(A_{i}, A_{i + 1}, A_{i + 2}\) のうち \(2\) つが同じ \(g\) 由来であるので、\(A_{i} + K \leq A_{i + 1}, A_{i} + K \leq A_{i + 2}, A_{i + 1} + K \leq A_{i + 2}\) のいずれかが成り立つことから示せます。

よって \(B, C\) はいずれも、\(i + 1\) 個のタイルを置いたときの左端の index を昇順に並べた列として成り立ちます。

\(B\) の index に沿ってタイルを置いたときの数の和を \(b\) とし、\(C\) の index に沿ってタイルを置いたときの数の和を \(c\) とします。

以下の自明に成り立つ式より、補題が成り立ちます。

\[f(i) + f(i + 2) = b + c \leq 2\max(b, c) \leq 2f(i + 1)\]

参考 : 以下のリンク先の補題 1

https://noshi91.github.io/algorithm-encyclopedia/d-edge-shortest-path-monge