[伯俊]2096号下り

11040 ワード
ダイナミックプログラミング テキストリンク

質問リンク


https://www.acmicpc.net/problem/2096

問題の説明


  • 3 xnから最低価格、最高価格
    • まで

    に答える


    に近づく

  • 最初は簡単なDPと考えられていたが、

    • 難関。

  • はそのままで、メモリが
    • を超えています.
  • もう少しで崩れそうになりましたが、心を静めて考えました.
  • 最初はnx 1の大きさではなくnx 3にしたいと思っていましたが、以前の経路も知る必要があることを知っていたのでだめでした.

    • 解決する

  • DPリストを考えると、以前の値を参照するだけでよいので、n個の
    • をする必要はない.
    2つの
  • 2 x 3を計算して位置を変えました

    困難。

  • でも最後に100%また間違った答えが出たので混乱しました

    • 解決する

  • の問題を見て、nが1なら間違っていることに気づきました.

    • コード#コード#

    import sys
read = sys.stdin.readline
n = int(read())
board = [list(map(int, read().split())) for _ in range(n)]
dp_max = [board[0], [0,0,0]]
dp_min = [board[0], [0,0,0]]

for y in range(1, n):

    dp_max[1][0] = max(dp_max[0][0], dp_max[0][1]) + board[y][0]
    dp_max[1][1] = max(dp_max[0]) + board[y][1]
    dp_max[1][2] = max(dp_max[0][1], dp_max[0][2]) + board[y][2]
    dp_max[0] = dp_max[1][:]
    
    dp_min[1][0] = min(dp_min[0][0], dp_min[0][1]) + board[y][0]
    dp_min[1][1] = min(dp_min[0]) + board[y][1]
    dp_min[1][2] = min(dp_min[0][1], dp_min[0][2]) + board[y][2]
    dp_min[0] = dp_min[1][:]
    
print(max(dp_max[0]), min(dp_min[0]))
    Vue.jsコンポーネントの再使用
    [TIL][SQL] SELECT-05