ABC 466 E - Range Flip

[KATO-Hiro]

問題の感想や気づきを投稿・共有するスペースです

[primesosu91]

dp[i番目まで見る][区間始まりが何回あったか][現在の表裏]を持ちながらDP
C++

for(int i = 0; i < n; i ++) for(int j = 0; j <= k; j ++) for(int l = 0; l <= 1; l ++){
    if(l == 0){
        dp[i+1][j][l] = max(dp[i][j][0], dp[i][j][1]) + A[i];
    }else{
        dp[i+1][j][l] = dp[i][j][1] + b[i];
        if(j>=1) dp[i+1][j][l] = max(dp[i+1][j][l], dp[i][j-1][0] + B[i]);
    }
}

[manuo-git]

あまり言及されていないDPで解いたので書きます。

DPの定義

カードを裏返すのではなく、i番目に $A_i$ or $B_i$ のカードを置くと考える。 $A_i$は一枚ずつ置き、 $B_i$ は合計 $K$ 区間まで区間で置くとすると以下のDPが出来る。

$dp_{i,k}$ : $i$ 番目まで置き終わって、 $B$ の区間を $k$ 個置いた時のカードの合計の最大値。

この値を $i$ の昇順に求める。

DPの遷移

Aの遷移

Aは一枚ずつ置くので $i-1$から遷移すれば良い。遷移する時に $A_i$ が足される。

$dp_{i,k} \gets dp_{i-1,k}+A_i$

Bの遷移

Bは区間で置くので、 $j(j<i)$ 番目から $i$ へ遷移する。 $S_i = \sum_{1\le j\le i}A_j$ とすると、遷移する時に $S_i-S_j$ が足される。

$dp_{i,k} \gets dp_{j,k-1}+S_i-S_j$

普通に $j(j<i)$ 全てを調べると $O(N)$ の計算量がかかるので、 $j$ 番目から遷移されてくる値を観察してみる。

$dp_{j,k-1}+S_i-S_j$

この中の $S_i$ は $i$ のみに依存する値なので $dp_{i,*}$ を計算する時に常に足す値として外に出せる。

残った $dp_{j,k-1}-S_j$ は $j,k-1$ に依存していて、 $B$ からの遷移で更新される $dp_{i,k}$ の値は結局 $j(j<i)$ を満たす $dp_{j,k-1}-S_j$ の最大値が採用される。

$i$ の昇順に調べていることを思い出すと、 $dp_{j,k-1}-S_j$ の値は $dp_{j,k-1}$ の値が確定した時に求めることが出来る。
この累積maxを $k(0<=k<K)$ 全てで保持しておけば、 $i$ 番目の遷移ではこの値を利用してDPの更新が出来る。

また、 $B$ の遷移ではこの累積maxの値を使うのでDPの値は $dp_{i-1,k}$ の値のみを保持しておけば良く、next DPが出来るのもうれしい。

Python(159ms)

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
INF = 1<<60
N, K = map(int, input().split())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

cum = [0]
for b in B: cum.append(cum[-1]+b)

dp = [-INF]*(K+1)
MX = [-INF]*(K+1)
MX[0] = 0
dp[0] = 0
for i in range(N):
    ndp = [-INF]*(K+1)
    for k in range(K+1):
        # A
        ndp[k] = max(ndp[k], dp[k]+A[i])
        if k == K: continue
        # B
        ndp[k+1] = max(ndp[k+1], cum[i+1]+MX[k])
    dp = ndp[:]
    for k in range(K+1):
        MX[k] = max(MX[k], dp[k]-cum[i+1])
print(max(dp))

[hibit-at]

Kadane のアルゴリズムによる解法です。

前からみた累積和最大値を保存した配列を P(Prefix) とします。
当初、P は単位元となる {-INF,-INF,-INF,...} です。

Kadane のアルゴリズムによって、P のプレフィクスとある配列 X とのサフィックスを比較して最大値を更新する処理を、以下「マージ」とします。

すべてが表の状態は、初期状態に対して A をマージした状態です。
このあと、
任意の区間を裏返す処理は
・Bをマージ
・Aをマージ
を行うのと同義です。

この裏返し処理を K 回行ったあとの P の末尾が答えとなります。

n,k = list(map(int, input().split(' ')))
AB = [list(map(int, input().split(' '))) for i in range(n)]
a,b = zip(*AB)
p = [-10**18] * (n+1)
def merge(x):
    for i in range(n):
        p[i+1] = max(p[i+1],max(0,p[i])+x[i])
merge(a)
for _ in range(k):
    merge(b)
    merge(a)
print(p[n])