競プロ典型90問 011 Gravy Jobs(★6)
貪欲法を用いると, 仕事は締め切りの早い順に行うか行わないか決めていくのが最適であるということがわかる(これに関連して, 区間スケジューリング問題という有名問題がある).
よって, 仕事をあらかじめ締め切りの早い順にソートしておく. すると, $ dp_{i, j} := $ i番目の仕事まで見て, 今$ j日終わっているとき($ j + 1日目の始めのとき)の報酬の最大値 としてDPをしていくことで答えを求められる. 遷移は仕事を行う場合と行わない場合に分けてしていけばよい.
よってこの問題を$ K = 5000として$ O(NK)で解くことができた.