BOJ 9465シール

18944 ワード
2022.01.08 DP 2021.01.14 テキストリンク
https://www.acmicpc.net/problem/9465
1秒、256 MBメモリ
input :
  • 試験盤ケース数T
  • n (1 <= n <= 100,000)
  • n個の整数(0<=マップ点数.<=100)
    • output :
    2本の
  • を共有しないシール点数の最値を出力します.
    • 条件:
  • のシールを1枚引き裂くと、上下左右のシールが引き裂かれ、使用できません
    取れる二つの行動(上り時)
    1.e,110/対角線を下に移動します.
    2.2グリッドを移動して下に移動します.
    下り時.
    1.,/対角線を上に移動します.
    2.2グリッドを移動して上へ移動します.
    サイドシフトは左側かもしれません.
    2022.01.08

    次の解

  • で取り外したシールや共有エッジのシールは使用できません.
  • すべての状況?
    • 特定の場所ですべての状況をチェックしてもいいですか?多すぎます.DPの使用
    反対の考えで特定の場所に着く方法.
    data[0][1]からdata[0][3]に移動すると.data[0][1]=>data[0][3]に移動するよりも、下に移動する値が大きい.
    そこで、上のコラムを下に、下を上に移動します.
    1グリッドまたは2グリッドを移動できます.3格?4格は?これ以上通ったほうが有利だ.だから2つの最小単位をチェックします.

    MAX関数。


    max関数を使用して、上下を計算します.
    0から計算を開始します.
    作成した動作に応じて、現在の基準で2つのスペースの後にチェックする必要があります.
    n=2の場合、1と0のすべての値をチェックする必要があります.
    1の値は事前に計算しておきます.
    	dp[0][0] = score[0][0]
    dp[1][0] = score[1][0]

    dp[0][1] = score[0][1] + dp[1][0]
    dp[1][1] = score[1][1] + dp[0][0]
    計算もあります.
    for i in range(2, n):
        dp[0][i] = max(dp[1][i - 1] + score[0][i], dp[1][i - 2] + score[0][i])
        dp[1][i] = max(dp[0][i - 1] + score[1][i], dp[0][i - 2] + score[1][i])
    その後dpを使うとメモリがたくさん消費されますscoreリストのみ使用します.
        score[0][1] += score[1][0]
    score[1][1] += score[0][0]

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

T = int(sys.stdin.readline())
result = []

for i in range(T):
    n = int(sys.stdin.readline())
    score = []

    for j in range(2):
        data = list(map(int, sys.stdin.readline().split()))
        score.append(data)

    score[0][1] += score[1][0]
    score[1][1] += score[0][0]

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

    result.append(max(score[0][n - 1], score[1][n - 1]))

for i in result:
    print(i)
    TIL#13.3.14標準問題
    11728.配列の組合せ