TopCoder SRM 588 Div1 Easy GUMIAndSongsDiv1
問題
n個の歌があり、それぞれの歌の長さはduration[i], トーンがtone[i]である。
Tの時間のうちに異なる歌をできるだけ多く歌いたい。
トーンがaである歌の直後にトーンがbの歌を歌おうとすると、|a - b|の時間の休憩が必要である。
最大でいくつの歌を歌えるか求めよ。
制約条件
n≦50
方針
歌う歌の集合を決定すると、その中ではトーンの小さい順に並べるのが最適。
なので、トーンを小さい順に並べてからDPすればいい。
DPは、dp[何曲歌ったか][直前の曲のトーン] := 最短時間
ソースコード
int dp[100][100]; class GUMIAndSongsDiv1 { public: int maxSongs(vector <int> duration, vector <int> tone, int T) { int n = tone.size(); int ans = 0; vector<pi> v; rep(i, n) v.pb(mp(tone[i], duration[i])); sort(all(v)); rep(i, n+1) rep(j, n+1) dp[i][j] = i == 0 ? 0 : inf; rep(i, n) for(int j = n; j >= 0; j--) rep(k, i + 1){ if(dp[j][k] == inf || j > 0 && i == k) continue; dp[j + 1][i] = min(dp[j + 1][i], dp[j][k] + v[i].second + (j ? v[i].first - v[k].first : 0)); if(dp[j + 1][i] <= T) ans = max(ans, j + 1); } return ans; } };