hotpepsiの練習帳

SRM 588

14:39

Div1 Easy (250) GUMIAndSongsDiv1

問題

• 音程と長さからなる歌がいくつか与えられる
• 連続して歌うとき、音程の差＋曲の長さの時間がかかる
• 時間Tで歌える最大の曲数を求める

方針

• 音程でソートしてDP
• コンテスト中は音程の差の扱いに迷って提出できず
• dp[最後に歌った曲のindex][曲数]=長さ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_588/GUMIAndSongsDiv1.cpp

結果

• 0pt 451st/696 rating 1205 -> 1183

典型問題なのだがパラメータが二つ出てくると弱い。