[伯俊]9465シール(Python)

質問する

尚根の妹は文房具屋で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辺を共有しないシール点数の最値を出力する.

に答える

liという名前のリストを作成して、入力した受信値とmaxリストという名前のリストを保存します.最初の値が含まれています.

maxリストに、li[0][0]+li[1]、li[1][0]+li[0][1]の値を入力します.

2番目の値を入力してもmax listより小さい1番目の値が表示されます.したがって、最初のマップの取り外し値が2番目のマップの取り外し値より大きいため、前の値を変数に入れます.

このように表現すれば、max_list[1].append(max(max_list[0][0],li[0][1]+max_list[0][1]))になります

コード#コード#

num = int(input())

for i in range(num):
    n = int(input())
    li = []
    li.append(list(map(int,input().split())))
    li.append(list(map(int,input().split())))

    max_list = [[] for i in range(n)]

    max_list[0] = [li[0][0],li[1][0]]

    for i in range(1,n):
        max_list[i].append(max(max_list[i-1][0],li[0][i]+max_list[i-1][1]))
        max_list[i].append(max(max_list[i-1][1],li[1][i]+max_list[i-1][0]))

    print(max(max_list[n-1]))