[BOJ] 9465
16749 ワード
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]))
前の値と前の値の最大値の間に...選択可能な最大値
オプション:対角線の値、その横の値
Reference
この問題について([BOJ] 9465), 我々は、より多くの情報をここで見つけました https://velog.io/@kinnyeri/BOJ-9465テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol