[アルゴリズム/標準]9465:シール(python)

0 1 2 3 4
50 40
30 100
1番のインデックスに左対角線の数を加えます.
次のインデックスから、左対角線の2つの数に1つのより大きな数を増やします.
dp[0][i] = max(dp[1][i-1], dp[1][i-2])
dp[1][i] = max(dp[0][i-1], dp[0][i-2])

for _ in range(int(input())):
    N = int(input())
    dp = [list(map(int, input().split()))for _ in range(2)]
    for i in range(1, N):
        if i == 1:
            dp[0][i] += dp[1][i-1]
            dp[1][i] += dp[0][i-1]
        else:
            dp[0][i] += max(dp[1][i-1], dp[1][i-2])
            dp[1][i] += max(dp[0][i-1], dp[0][i-2])
    print(max(dp[0][N-1],dp[1][N-1]))