kojingharangの日記

SRM 588 Div1 250 GUMIAndSongsDiv1

09:42 |

• 歌の長さD[i]、歌の音の高さtone[i]が与えられる。歌と歌の間にはtoneの差だけ時間をおかないといけない。
• 時間T以内で沢山歌いたい。何曲歌えるか。
• 1≦N≦50, 1≦D[i]≦100,000, 1≦tone[i]≦100,000, 1≦T≦10,000,000

• 歌の長さでソート（間違い）
• dp[i][j][n] ... 歌iまで考慮したときに、最後に歌ったのが歌jで、歌った曲数がnの時の最小時間
• で、最後に表を見て最小時間が T 以内のもので最大の n が答え
• という方針。

• 最後のサンプルが合わない

(あとで)

• tone でソートしておくらしい。
• DPでは直前の歌と今の歌から最小時間を更新していって任意の歌の集合を歌った時の最小時間を求めるわけで、歌の集合が決まったとしてそれらを歌う時間が最小になる順番はtoneでソートした順だからだろう。

• accepted in practice

class GUMIAndSongsDiv1 {
	public:
	int maxSongs(vector <int> D, vector <int> tone, int T) {
		int N=D.size();
		VVI dp(N, VI(N+1, 1<<30));
		vector<PII> w;
		REP(i, N) w.PB(MP(tone[i], D[i]));
		sort(ALL(w));
		REP(i, N) D[i]=w[i].second, tone[i]=w[i].first;
		REP(i, N) {
			dp[i][0] = 0;
			dp[i][1] = D[i];
			RANGE(n, 2, N+1) {
				REP(j, i) {
					dp[i][n] = min(dp[i][n], dp[j][n-1] + D[i] + abs(tone[i]-tone[j]));
				}
			}
		}
		int ans = 0;
		REP(i, N) REP(n, N+1) if(dp[i][n]<=T) ans = max(ans, n);
		return ans;
	}
};

ツイートする