内容

ABC145のE問題(500点)「All you can eat」をpython出といた。
提出はpypy
問題

atcoder.jp

考えたこと

ナップサックな感じだし、制約がN=3000なので、N**2でできそうなDPを思いつく。
T-1に頼んだものは、食べ終わることができる。
- 料理を頼んだ時、その順番は、一番時間がかかるものが最後になった方が良さそう。
  - 料理を、「かかる時間」の小さい順にsortしてdpしていく。
    ポイント
かかる時間の小さい順にsortする。
dpの更新の時、食べ始める時間のループは、reversedする
- tを小さい方から更新した場合、そのループで更新した結果を使って、新しい更新ができてしまうから。

実装

N,T = map(int,input().split())
item=[list(map(int,input().split())) for _ in range(N)]
#食べるのにかかる時間が小さい順にsort
item=sorted(item,lambda x:x[0])

#dp[i]=i分までに食べきることができる　美味しさの最大値
#dp[T]は、T-1までに頼んでいて、時刻T以降に食べ終わる場合をまとめている。
dp=[0]*(T+1)

for a,b in item:
    #1次元dpで、小さい方から更新していくと、更新後の結果を使って新しい更新ができてしまうから、reverse
    for t in reversed(range(T)):#食べ始める時間(0~T-1)
        dist=min(T,t+a)#食べ終わる時間。Tを超える場合はTにする。(dist[T]からは遷移しないので、T以上をTにまとめる。
        dp[dist] = max(dp[t]+b,dp[dist])
print(max(dp))