問題:D - 映画の連続視聴
解答:Submission #15529217 - Code Formula 2014 本選
解法:それなりに探索しないといけなそう。DPを行う。
前処理として、時間0と終了時間を含む(重複のない)配列を作成しておき、また終了時間からその配列のインデックスが分かるようにしておく。 dp[x]:終了時間(インデックス)xの時の幸福度の最大値とし、配るDPを行う。
配る元を終了時間(インデックス)iとするとき、配る先は各映画の種類について、その映画を連続で1回、2回、3回…見た後の終了時間のうちそれぞれ最も早い時間(インデックス)である。これは映画の種類ごとに終了時間の速い順にソートしておき、貪欲に映画をみるシミュレーションをすればよい(区間スケジューリング)。
計算量はおそらく、各終了時間のDPループがO(N)、それぞれのループ内では毎回その時間からの区間スケジューリングのシミュレーションが行われるが、シミュレーションで各映画が使用される回数は高々1回であるためO(N)、合わせてO(N2)となり間に合う(多分)。