BOJ 2096降格

質問する

BOJ 2096降格
金色IV|白駿2096|Python 3糸草

アルゴリズム#アルゴリズム#

簡単なDPの問題、またはメモリの制限は4 MBで、非常に小さいです.
すなわち,スライドウィンドウ技術を用いるべきである.スライドウィンドウは、ネットワーク上にバッファを構成する方法で、アルゴリズムはメモリの使用量を減らすために使用します.
上の図に示すように、DPアレイは通常構成される.(ほとんどの場合、十分なメモリを提供できるため)
メモリ制限が小さいという問題は、不要な部分を捨ててメモリを節約する必要があります.右図に示すように、DPアレイの一部のみが実現され、全体図では、部分アレイは下降し続ける.
この問題では、現在のDP行を得るためには、前のDP行の情報のみが必要となるため、前のDP行の上(前)の情報は破棄される.つまり、2行を切り替えてスライドウィンドウを実現します.

コード#コード#

import sys

input = sys.stdin.readline

N = int(input())

MaxDP = [[0, 0, 0], [0, 0, 0]]
MinDP = [[0, 0, 0], [0, 0, 0]]

scores = list(map(int, input().split()))

MaxDP[0][0] = scores[0]
MaxDP[0][1] = scores[1]
MaxDP[0][2] = scores[2]
MinDP[0][0] = scores[0]
MinDP[0][1] = scores[1]
MinDP[0][2] = scores[2]

for _n in range(1, N):
    scores = list(map(int, input().split()))
	
    # DP값 계산
    MaxDP[1][0] = scores[0] + max(MaxDP[0][0], MaxDP[0][1])
    MaxDP[1][1] = scores[1] + max(MaxDP[0])
    MaxDP[1][2] = scores[2] + max(MaxDP[0][1], MaxDP[0][2])

    MinDP[1][0] = scores[0] + min(MinDP[0][0], MinDP[0][1])
    MinDP[1][1] = scores[1] + min(MinDP[0])
    MinDP[1][2] = scores[2] + min(MinDP[0][1], MinDP[0][2])
	
    # 행 교체 (슬라이딩 윈도우) 필요없는 정보는 버림
    MaxDP[0][0] = MaxDP[1][0]
    MaxDP[0][1] = MaxDP[1][1]
    MaxDP[0][2] = MaxDP[1][2]
    MinDP[0][0] = MinDP[1][0]
    MinDP[0][1] = MinDP[1][1]
    MinDP[0][2] = MinDP[1][2]

print(max(MaxDP[0]), min(MinDP[0]))

結果

スライドウィンドウを使用しないと、メモリオーバーフローが発生します.