AtCoder Beginner Contest 125 D - Flipping Signs

programing

はじめに

過去問をやっていたらDPを利用する問題と当たった。
atcoder.jp

最近DPはちょっと練習していたが解けなかったので復讐をかねて書き残す。

解法

今回はいわゆる「貰うDP」で解いていく。
DP配列として以下の配列を用意する。

dp[i][j] (i \in \{0,1,...,N\}, j \in \{0,1\})

ここで、 dp[i+1][j] を決定する際に、 dp[i+1][0] は符号を反転しない状態、 dp[i+1][1] は符号を反転する状態とする。

このとき、 dp[i+1][0]を求める際に利用する A[i]は、 A[i-1]が符号を反転していなかった場合 A[i]、反転していた場合 -A[i]となる。

また、 dp[i+1][1]を求める際に利用する A[i]は、 A[i-1]が符号を反転していなかった場合 -A[i]、反転していた場合 A[i]となる。

よって、 dp[i+1][0]と dp[i+1][1\はそれぞれ以下のように求めることができる。

dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i])
dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])

コードは以下のようになった。

N=int(input())
A=list(map(int,input().split()))
dp=[[0]*2 for _ in range(N+1)]
dp[0][1]=-float("inf")
for i in range(N):
  dp[i+1][0]=max(dp[i][0]+A[i],dp[i][1]-A[i]) 
  dp[i+1][1]=max(dp[i][0]-A[i],dp[i][1]+A[i])
print(dp[-1][0])

おわり。