SRM 588 div 1
easy撃墜されて0pointだった
1225 -> 1194
easy
N=1のケースで撃墜されるコードを書いてしまった。
DP思いつかない人なので貪欲で解いた。
最大m個の歌を歌えるとして
a1, a2, a3, ... , am
の歌を歌うのにかかる時間Sは
S = Σ(duration) + Σ(wait_time)
= Σ(duration) + max(tone[ai]) - min(tone[aj])
となるので、歌をtoneでソートしてmaxとminのtoneを決めてしまってから、そのtoneの範囲にある歌のdurationを小さい順に合計がTを超えるまで見ていけばいい。
#include <cstdio> #include <algorithm> #include <vector> #include <string> #include <queue> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) #define F first #define S second typedef pair<int, int> P; class GUMIAndSongsDiv1{ public: P songs[50]; int N; int solve(int p, int q, int T){ int dur[50]; int m = q - p + 1; for(int i = p; i <= q; i++){ dur[i-p] = songs[i].S; } sort(dur, dur + m); int sum = 0; rep(i, m){ sum += dur[i]; if(sum > T) return i; } return m; } int maxSongs(vector <int> duration, vector <int> tone, int T){ N = tone.size(); rep(i, N){ songs[i].F = tone[i]; songs[i].S = duration[i]; } sort(songs, songs + N); int ans = 0; rep(i, N){ for(int j = i; j < N; j++){ int sw = songs[j].F - songs[i].F; ans = max(ans, solve(i, j, T - sw)); } } return ans; } };