[PS]Baek Jun 9465シール

質問する

BJ 9465シール
質問分類:DP
質問難易度:シルバー1

問題コード

import sys
from collections import deque
import itertools
import heapq

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

k = int(input())
ans = []

for kk in range(k):
    n = int(input())
    g = [list(map(int, input().split())) for _ in range(2)]
    dp = [item[:] for item in g]

    if n != 1:

        dp[0][1] += g[1][0]
        dp[1][1] += g[0][0]

        for i in range(2, n):
            dp[0][i] += max(dp[1][i-2], dp[1][i-1])
            dp[1][i] += max(dp[0][i-2], dp[0][i-1])

    ans.append(max(dp[0][n-1],dp[1][n-1]))

print(*ans, sep = '\n')

問題の復記&感じ

注意:典型的なDP問題は、適切な順序で並べ替えられる.
以前に解いた問題のようにcaseを適切に区分し,特定の時点の最大値に保存する.以前の問題と解決できる差は少ないと思っていたので、点火式を誘導するためにいろいろ試してみましたが、思いつきませんでした.
重要なのは,問題制限に違反しない場合に,特定の時点の最大値の感覚を有機的に導出できることである.