atcoder ABC 306 D - Poisonous Full-Courseの間違い例と正解例

atcoder.jp

・解説：
Editorial - Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）

・反省点：食べたときと食べなかったときの遷移は別々にやるとWA。食べたときの遷移をして、食べたとき(dp[i+1][0],dp[i+1][1])と食べなかったとき（dp[i][0],dp[i][1]）どちらが大きいか、見る必要がある。

・間違ったコード

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]

dp=[[0 for _ in range(2)] for _ in range(n+1)]
dp[0][0]=0

for i in range(n):
  if xy[i][0]==1:
    dp[i+1][1]=max(dp[i+1][1],dp[i][1],dp[i][0]+xy[i][1])
    dp[i+1][0]=dp[i][0]
    
  if xy[i][0]==0:
    dp[i+1][0]=max(dp[i+1][0],dp[i][0]+xy[i][1],dp[i][1]+xy[i][1])
    dp[i+1][1]=dp[i][1]

  #print(dp[i+1][0],dp[i+1][1])
print(max(dp[n][0],dp[n][1]))

・ACのコード

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]

dp=[[0 for _ in range(2)] for _ in range(n+1)]
dp[0][0]=0

for i in range(n):
  #食べたとき
  if xy[i][0]==1:
    dp[i+1][1]=dp[i][0]+xy[i][1]
    
  if xy[i][0]==0:
    dp[i+1][0]=max(dp[i][0]+xy[i][1],dp[i][1]+xy[i][1])
  
  #食べたとき(dp[i+1][0],dp[i+1][1])と食べなかったとき（dp[i][0],dp[i][1]）どちらが大きいか。
  dp[i+1][0]=max(dp[i+1][0],dp[i][0])
  dp[i+1][1]=max(dp[i+1][1],dp[i][1])
  
  #print(dp[i+1][0],dp[i+1][1])
print(max(dp[n][0],dp[n][1]))