ABC466 E - Range Flip

区間反転

考え方

問題を少し言いかえれば、これは単純な動的計画法の問題である。

カード列の $l$ 枚目から $r$ 枚目を裏返す操作をしていいとされている。
これは、実は、$l$ 枚目から右を全て裏返し、さらに $r+1$ 枚目から右を全て裏返すとも考えられる。
（$r$ がカード列の右端の場合は、なにもしないことに相当する）

つまり、「あるカードから右を全て裏返す」を最大 $2K$ 回行って、最大値はいくつか？」を解けばよい。
厳密には偶数回限定であるが、何もしないに相当する操作も選べるため、実質的に奇数回も許される。

ということで、長さ $2K+1$ のテーブルを持ち、左から $1$ 枚ずつ見ながら更新していけばよい。
$i$ 番目のデータは、そこより左で反転を $i$ 回行った場合の最大値。
つまり、直前のデータの $i$ 回のデータと $i-1$ 回のデータの大きい方に、次のカードの値を足せばよい。

全てのカードを見終わった後で、テーブルの任意の位置にある値の最大値が答え。
計算量は $O(NK)$。

入力を受け取る。

n: 7
k: 2
a: {2, 6, 3, 9, 4, 7, 5}
b: {1, 9, 5, 2, 8, 3, 6}

$2K+1=5$ 個の状態を持つ。
最初は、反転の境界をまだ通過していない状態だけが $0$ である。

$$(0,-\infty,-\infty,-\infty,-\infty)$$

$1$ 枚目では、$0$ 回の状態からは表の値 $2$ を使う。
また、ここで反転を開始する場合は裏の値 $1$ を使う。

0回: 0+2=2
1回: 0+1=1

したがって、$1$ 枚目まで見た状態は次のようになる。

$$(2,1,-\infty,-\infty,-\infty)$$

$2$ 枚目では、例えば反転境界を $1$ 回通過した状態を考える。
$1$ 回のまま進む場合と、$0$ 回からここで反転する場合を比べる。

1回: max(1,2)+9=11
2回: max(-∞,1)+6=7

同様に更新を続けると、各カードを見た後の状態は次のようになる。

見た枚数	$0$ 回	$1$ 回	$2$ 回	$3$ 回	$4$ 回
$0$	$0$	$-\infty$	$-\infty$	$-\infty$	$-\infty$
$1$	$2$	$1$	$-\infty$	$-\infty$	$-\infty$
$2$	$8$	$11$	$7$	$-\infty$	$-\infty$
$3$	$11$	$16$	$14$	$12$	$-\infty$
$4$	$20$	$18$	$25$	$16$	$21$
$5$	$24$	$28$	$29$	$33$	$25$
$6$	$31$	$31$	$36$	$36$	$40$
$7$	$36$	$37$	$41$	$42$	$45$

最後の状態の最大値は $45$ なので、答えは $45$ となる。

答えは、int 型からはみ出る。
DP テーブルを含め、long long 型を用いること。

特になし。