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;
	}
};