カード \(l, l + 1, \ldots, r - 1\) のことを単に区間 \([l, r)\) と呼びます。

まず、操作する区間には交わりがないとしてよいです。これは、最適解のうち操作する区間の長さの和が最小であるものを取ったとき、区間どうしは交わらないことから従います。実際、交わりが空でない \(2\) つの区間 \([l_1, r_1)\) と \([l_2, r_2)\) に対して操作を行っているとき、\([l_1, r_1), [l_2, r_2)\) を \([\min(l_1, l_2), \max(l_1, l_2)), [\min(r_1, r_2), \max(r_1, r_2))\) に置き換えるとカードの向いている向きは変わりませんが、区間の長さの和が減少するため最小性に矛盾します（置き換え後の区間が空になることもありますが、この場合は単に操作をしないことにすればよいです）。

したがって、本問題は以下の問題に帰着されます。

カード \(1,2,\ldots,N\) を（空でもよい） \(2K + 1\) 個の区間に分割する。左から奇数番目の区間に属するカードでは表面が上を向いており、左から偶数番目の区間に属するカードでは裏面が上を向いている。カードの上を向いている面に書かれている数の和として考えられる最大値を求めよ。

あるいは、\(1\) 番目以外の区間は空でない \(2K + 1\) 個以下の区間に分割すると考えても同様です。

これは \(dp_{i, j}\) を \(i\) 番目のカードが \(j\) 番目の区間に属するときのカード \(1, 2, \ldots, i\) の上を向いている面に書かれている数の和として考えられる最大値とする動的計画法により計算することができます。時間計算量は \(O(NK)\) です。