質問リンク

https://www.acmicpc.net/problem/9465

問題の説明

2行N列マザーボード

枚ごとに得点

が選択されている場合、隣接するマップ

は選択できません.

分の最低価格出力

に答える

dp[0][0], dp[1][0], dp[0][1], ... スコア

を順番に計算

はいずれにしても上下同時に選択できないので、

を別々に考える.
座標の最長値

に保存

上方の場合
座標

が選択された場合

左下隅は選択不可(左下隅に最も近い)+(現在のシール点数)

座標

が選択されていない場合

最大値(左上および左下)

下向きの場合
座標

が選択された場合

(左上隅に最も近い)+(現在のシール点数)

座標

が選択されていない場合

最大値(左上隅と左上隅)

に感銘を与える

最初は質問がよく分かりませんでした

を使うのは何ですか...

を選んだだけだ

DPを使うべきだと思いますが、どうやって実現すればいいのか少し悩んでいます.

繰り返し文の順序は、行ではなくまず列を行うべきであると考えられ、

.

コード#コード#

import sys


def init():
    n = int(ipt())
    board = [list(map(int, ipt().split())) for _ in range(2)]
    dp = [[0] * n for _ in range(2)]
    dp[0][0] = board[0][0]
    dp[1][0] = board[1][0]
    return n, board, dp


ipt = sys.stdin.readline
tc = int(ipt())
for _ in range(tc):
    n, board, dp = init()
    for x in range(1, n):
        for y in range(2):
            if y % 2 == 0:
                dp[y][x] = max(
                    board[y][x] + dp[y+1][x-1], 
                    max(dp[y][x-1], dp[y+1][x-1])
                )
            else:
                dp[y][x] = max(
                    board[y][x] + dp[y-1][x-1], 
                    max(dp[y-1][x-1], dp[y][x-1])
                )
    print(max(map(max, dp)))