白駿1932-整数三角形


提问链接


Code

import sys
from collections import deque
read = sys.stdin.readline

tri = []
n = int(read())
for _ in range(n):
    tri.append(list(map(int, read().split())))

ans = deque([tri[0][0]])
for i in range(1, n):
    for j in range(i):
        num = ans.popleft()
        if j==0:
            ans.append(num+tri[i][j])
        else:
            ans[-1] = max(ans[-1], num+tri[i][j])
        ans.append(num+tri[i][j+1])
print(max(ans))

困難事項

  • 分割征服の方法で解決した.
  • elseセクションは、コードのコアセクションです.