[BOJ] 9465


DPだと知っただけで残りは分からない
質問する

me

import sys
input = sys.stdin.readline

T= int(input())

for _ in range(T):
    n = int(input())
    stickers=[list(map(int,input().split())) for _ in range(2)]
    flag=-1 # 아직 flag 세우지 못함
    sums=[[0]*n for _ in range(2)]
    for i in range(n):
        # flag는 항상 앞으로 더할 flag
        # 다른 flag가 클 때
        noFlagSum=0
        sums[0][i]=sums[1][i-1]+stickers[0][i]
        sums[1][i]=sums[0][i-1]+stickers[1][i]
        if sums[0][i] > sums[1][i]: flag=1
        elif sums[0][i] < sums[1][i]: flag=0
        if i>1: # 2부터
            max_before= max(sums[0][i - 2], sums[1][i - 2])
            max_now = max(stickers[0][i],stickers[1][i])
            print(i,max_before,max_now)
            if sums[(flag+1)%2][i] <= max_before+max_now:
                # 현재 최대 값 <= 그 이전 것 + 현재 값 (이전은 선택하지 않는)
                for j in range(2):
                    sums[j][i] = max_before+max_now
                flag = -1
    for s in sums: print(s)
    print(max(sums[0][-1],sums[1][-1]))
選択なし...
どこが間違っているのかわからない
明日見てから知ります.ううう

others


ソース
t = int(input())
for i in range(t):
  s = []
  n = int(input())
  for k in range(2):
    s.append(list(map(int, input().split())))
  for j in range(1, n):
    if j == 1:
      s[0][j] += s[1][j - 1]
      s[1][j] += s[0][j - 1]
    else:
      s[0][j] += max(s[1][j - 1], s[1][j - 2])
      s[1][j] += max(s[0][j - 1], s[0][j - 2])
  print(max(s[0][n - 1], s[1][n - 1]))
前の値と前の値の最大値の間に...
選択可能な最大値
オプション:対角線の値、その横の値