SRM588Div1Easy
問題
N個の曲と時間Tが与えられる。各曲にはdurationとtoneが与えられており、T秒間だけ曲を流すことができる。durationは曲の長さを秒で示す。現在の曲がtone[i]で次の曲がtone[j]だとすると、次の曲に移るのに|tone[i]-tone[j]|秒必要とする。
T秒間の間にながせる曲の最大値を求めよ。
解法
toneの範囲を指定し、その中でdurationが短いものから順に選択していく。toneの範囲を与えられた曲の組み合わせで全探索することで答えが求まる。
計算量
