2008年 日本情報オリンピック春合宿OJ nile - Nile.Com【Python】

問題はこちら。

いかにもdpだけど持ち方に工夫がいる。

dp[i][d][n] = d日目に店舗nからi日以上連続で購入し、d日目にi日連続購入割引を適用したときの最小費用 --- ①

とするとうまくいく。なにやら複雑だが

dp[i][d][n] = d日目に店舗nからi日以上連続で購入したときの最小費用

とすると遷移がややこしくなってしまうので①のように持つ。

古い問題はメモリ制約が厳しいので節約のためにdを落とす。

import sys
readline = sys.stdin.readline

def main():
   INF = float('inf')
   N, D = map(int, readline().split())
   
   dp = [[INF]*N for _ in range(3)]
   for d in range(D):
       cost = list(map(int, readline().split()))
       if d == 0:
           min_cost = 0
       else:
           min_cost = min(min(dp[0]), min(dp[1]), min(dp[2]))
       for n in range(N):
           dp[0][n], dp[1][n], dp[2][n] = \
           min_cost + cost[n], \
           dp[0][n] + cost[n]*9 // 10, min(dp[1][n], \
           dp[2][n]) + cost[n]*7 // 10
           
   ans = min(min(dp[0]), min(dp[1]), min(dp[2]))
   print(ans)
   
if __name__ == "__main__":
   main()