BOJ::シール(no.9465)

質問する

尚根の妹は文房具屋で2 n枚のシールを買った.シールは図(a)に示すように2行n列に並べられている.やさしい人はシールで机を飾ります.
やさしく購入したシールの質が悪い.シールを1枚引き裂くと、それらのシールと共有エッジのシールが引き裂かれ、使用できません.つまり、外したシールの左、右、上、下のシールは使用できません.

すべてのシールが貼れない優しさは各シールに点数をつけ、点数の和が最大に達し、シールを引き裂きたいと思っています.まず、図(b)のように各シールに点数をつけます.やさしいシール点数の最値を求めるプログラムを作成してください.すなわち,2 n個のマップのうち,スコアの和が最大であり,互いに共有しないエッジのセットを求める必要がある.
上図では、点数50、50、100、60のシールを選択した場合、点数は260となり、これが最大点数となります.点数が一番高い2枚のシール(100と70)はエッジを共有しているので、同時に分けることはできません.

入力

第1行は、試験例の個数Tを与える.各テストケースの最初の行にはn(1≦n≦100000)が与えられる.次の2行にはn個の整数があり、各整数はその位置に対応するシールの点数である.連続する2つの整数の間にスペースがあります.分数が0以上、100以下の整数.

しゅつりょく

各試験例は、2 n個のシールのうち、2辺を共有しないシール点数の最値を出力する.

🤔 の意見を打診

これは絵を描いて考えます.

注釈

dp[i][j]:i行j列を除くと、シール点数の最値は

ヶーシング

左対角線

左折対角線
考えるべきだ.

上記の例図から最後の60を削除する.
ではまず10と40は使えませんが、前に外したシールは20か100です.
△70度でもいいですが、20度の位置を通らないと、最高値にはなりません.
つまり、最後のシールの左対角線方向に無条件に1つ通さなければ、最低価格を形成できない.
🔥 てんかしき
dp[1][i] += max(dp[0][i-1], dp[0][i-2])
dp[0][i] += max(dp[1][i-1], dp[1][i-2])

📌 説明する

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    dp = []
    dp.append([0]+list(map(int, input().split())))
    dp.append([0]+list(map(int, input().split())))

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

    print(max(dp[0][-1], dp[1][-1]))