BOJ 2096降格

11938 ワード
2021.03.07 テキストリンク
https://www.acmicpc.net/problem/2096
1秒、4 MBメモリ
input :
  • N(1 ≤ N ≤ 100,000)
  • N行には、
    • という3つの数字があります.
    output :
  • は最高点と最低点に分け、
    • を出力する.
    条件:



  • 上記のように移動可能です.
    • 各位置で発生する可能性のある最低価格と、最高価格を見つけて、各配列の価格を更新します.
    dpmax = max(dpmax[0], dpmax[1]) + data[i][0], max(dpmax) + data[i][1], max(dpmax[1], dpmax[2]) + data[i][2]
dpmin = min(dpmin[0], dpmin[1]) + data[i][0], min(dpmin) + data[i][1], min(dpmin[1], dpmin[2]) + data[i][2]
    位置は0:0,1であり、max+data[i][0](0番目の位置の値)
    位置は1:0、1、2個のmax+data[i][1](最初の位置の値)
    位置は2:1、2個max+data[i][2](2番目の位置の値)
    長さが3に固定されているので、この3つのケースを含めましょう.
    また,このメモリ条件が小さいため,dpのサイズ自体が小さいはずである.
    この場合、1次元配列を更新し続ける方法を使用する必要があります.
    import sys

n = int(sys.stdin.readline())
data = []

for i in range(n):
    data.append(list(map(int, sys.stdin.readline().split())))

dpmax = [data[0][0], data[0][1], data[0][2]]
dpmin = [data[0][0], data[0][1], data[0][2]]

for i in range(1, n):
    dpmax = max(dpmax[0], dpmax[1]) + data[i][0], max(dpmax) + data[i][1], max(dpmax[1], dpmax[2]) + data[i][2]
    dpmin = min(dpmin[0], dpmin[1]) + data[i][0], min(dpmin) + data[i][1], min(dpmin[1], dpmin[2]) + data[i][2]
print(max(dpmax), min(dpmin))
    2021.10.06.水曜開発ログ
    [プログラマーSQLハイスコアKit]名前のついた動物のID