下へ

区分アルゴリズム:ダイナミックプログラミング、スライドウィンドウ

問題を解く:問題内容から次の行に降格する際の制約条件を明確に規定し,この条件の下で最大点数と最小点数の内容を探すことにより,これを点火式による動的プログラミング問題と見なして行う.ここで最も注意しなければならない部分は問題の基本条件です.メモリ制限は4 MBです.つまり、問題を解決する方法は、ダイナミックプログラミングだけでなく、メモリを最小限に抑えることです.
メモリが限られている場合は、各行のスコアが2 Dリストとして入力された後、同じサイズのdpリストを繰り返し文で最大dpリストと最小dpリストとして作成し、それぞれ作成した点火式を調整できます.
メモリを最小化するには、リスト内のメモリを最小限に抑えることがコアであるため、入力するたびにdpリストをすぐに埋め込むことができます.そして、各最大、最小dpリストにおいて、2*3サイズのリストにおいて、dp[0]は前の行に計算された値を表し、dp[1]は前の行の最大または最小値+現在の行の値の和を記憶できることを表し、その後、dp[0]=dp[1]により計算された現在までの値を前の行の位置に移動する.
ソース:

import sys

n = int(sys.stdin.readline())

dp = [[0] * 3 for _ in range(2)]
dpMin = [[0] * 3 for _ in range(2)]
for i in range(n):
    line = list(map(int, sys.stdin.readline().split()))

    dp[1][0] = line[0] + max(dp[0][0], dp[0][1])
    dp[1][1] = line[1] + max(dp[0][0], dp[0][1], dp[0][2])
    dp[1][2] = line[2] + max(dp[0][1], dp[0][2])

    dpMin[1][0] = line[0] + min(dpMin[0][0], dpMin[0][1])
    dpMin[1][1] = line[1] + min(dpMin[0][0], dpMin[0][1], dpMin[0][2])
    dpMin[1][2] = line[2] + min(dpMin[0][1], dpMin[0][2])

    dp[0][0], dp[0][1], dp[0][2] = dp[1][0], dp[1][1], dp[1][2]
    dpMin[0][0], dpMin[0][1], dpMin[0][2] = dpMin[1][0], dpMin[1][1], dpMin[1][2]

print(max(dp[1]), min(dpMin[1]))

注意事項
deepcopyモジュールを使用して深さコピーを行いたいと思っていました.
これは逆にメモリオーバーフローに影響します.
最小限のメモリが必要な場合は、
問題を排除して解決すべきらしい.

題出所:https://www.acmicpc.net/problem/20962

カイドウ草が白駿で「そうだ!!」判定を受けた