ABC466 E - Range Flip

考え方

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

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

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

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

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

入力例1での動作

入力を受け取る。

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

$2K+1=5$ 個の状態を持つ DP テーブルを用意する。
最初は、境界を $0$ 回通過した状態だけを 0 とする。

dp: {0, -INF, -INF, -INF, -INF}

$1$ 枚目のカードを処理する。
各要素について、自身と $1$ つ前の要素の大きい方に、カードの値を足す。
境界通過回数が偶数なら a[0]、奇数なら b[0] を足す。

dp[0]: 0+2=2
dp[1]: max(-INF,0)+1=1
dp[2]: max(-INF,-INF)+2=-INF
dp[3]: max(-INF,-INF)+1=-INF
dp[4]: max(-INF,-INF)+2=-INF

dp: {2, 1, -INF, -INF, -INF}

$2$ 枚目のカードを処理する。
境界通過回数が偶数なら a[1]、奇数なら b[1] を足す。

dp[0]: 2+6=8
dp[1]: max(1,2)+9=11
dp[2]: max(-INF,1)+6=7
dp[3]: max(-INF,-INF)+9=-INF
dp[4]: max(-INF,-INF)+6=-INF

dp: {8, 11, 7, -INF, -INF}

$3$ 枚目のカードを処理する。
境界通過回数が偶数なら a[2]、奇数なら b[2] を足す。

dp[0]: 8+3=11
dp[1]: max(11,8)+5=16
dp[2]: max(7,11)+3=14
dp[3]: max(-INF,7)+5=12
dp[4]: max(-INF,-INF)+3=-INF

dp: {11, 16, 14, 12, -INF}

$4$ 枚目のカードを処理する。
境界通過回数が偶数なら a[3]、奇数なら b[3] を足す。

dp[0]: 11+9=20
dp[1]: max(16,11)+2=18
dp[2]: max(14,16)+9=25
dp[3]: max(12,14)+2=16
dp[4]: max(-INF,12)+9=21

dp: {20, 18, 25, 16, 21}

$5$ 枚目のカードを処理する。
境界通過回数が偶数なら a[4]、奇数なら b[4] を足す。

dp[0]: 20+4=24
dp[1]: max(18,20)+8=28
dp[2]: max(25,18)+4=29
dp[3]: max(16,25)+8=33
dp[4]: max(21,16)+4=25

dp: {24, 28, 29, 33, 25}

$6$ 枚目のカードを処理する。
境界通過回数が偶数なら a[5]、奇数なら b[5] を足す。

dp[0]: 24+7=31
dp[1]: max(28,24)+3=31
dp[2]: max(29,28)+7=36
dp[3]: max(33,29)+3=36
dp[4]: max(25,33)+7=40

dp: {31, 31, 36, 36, 40}

$7$ 枚目のカードを処理する。
境界通過回数が偶数なら a[6]、奇数なら b[6] を足す。

dp[0]: 31+5=36
dp[1]: max(31,31)+6=37
dp[2]: max(36,31)+5=41
dp[3]: max(36,36)+6=42
dp[4]: max(40,36)+5=45

dp: {36, 37, 41, 42, 45}

境界を通過する回数は $2K$ 回以下なら何回でもよい。
よって、DP テーブル全体の最大値 $45$ が答え。

注意点

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

別解

特になし。