(DP)白駿9465号シール
6530 ワード
tc = int(input())
for _ in range(tc):
n = int(input())
dp = []
for _ in range(2):
dp.append(list(map(int, input().split())))
dp[0][1] += dp[1][0]
dp[1][1] += dp[0][0]
for i in range(2, n):
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]))たとえば
dp[0][3]の最大値のステップ
dp[1][2]またはdp[1][1]の値は最大値であるべきである.
index 0 1 2 3 4
0 50 10 + 30 = 40 max(100, 30) + 100 = 200 max(120, 100) + 20 = 140 max(210, 120) + 40 = 250
1 30 50 + 50 = 100 max(40, 50) + 70 = 120 max(200, 40) + 10 = 210 max(140, 200) + 60 = 26
入力例2)
index 0 1 2 3 4 5 6
0 10 30+ 20= 50 max(20, 50) + 10= 60 max(50, 80) + 50= 130 max(80, 110) + 100= 210 .. ..
1 20 40+ 10= 50 max(10, 50) + 30= 80 max(50, 60) + 50= 110 max(60, 130) + 60 = 190 .. ..
Reference
この問題について((DP)白駿9465号シール), 我々は、より多くの情報をここで見つけました https://velog.io/@jwun95/DP-백준-9465번-스티커テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol