PythonでJOI難易度6を埋める #6

メモリが厳しい．

nile - ナイルドットコム (Nile.Com)

問題文から溢れるDP臭．愚直なDPにするとになったから，うまく更新回数を減らす必要がある．
そこで，日目に新しく行くお店(連続して買わないお店)は，前日の最も安い要素から移動することに注目する．そうすると，それぞれの日ごとにその日の最小値を計算して，次の日の計算に使えばよいことが分かる．
TLEの次はMLEが待っています．雑に配列を作るとMLEで弾かれるので，dp[連続で買ってる回数][お店の番号]だけで管理します．

n, d = map(int, input().split())

dp = [[float('inf')] * n for _ in range(3)]

for i in range(d):
    price = list(map(int, input().split()))
    if i == 0:
        pre_min = 0
    else:
        pre_min = min(min(dp[0]), min(dp[1]), min(dp[2]))
    for j in range(n):
        dp[0][j], dp[1][j], dp[2][j] = pre_min + price[j], dp[0][j] + price[j] * 0.9, min(dp[1][j], dp[2][j]) + price[j] * 0.7

ans = min(min(dp[0]), min(dp[1]), min(dp[2]))
print(int(ans))

参考にした記事