DP苦手な水コーダーがはまったので、ざっと解説を書いておきます。
問題のリンクはこちらです
解説
AC解法に辿り着くまでにいろんな誤解法を思いついたのですが、長くなりそうなのでAC解法のみ記します。
まず、次のようなDPテーブルを考えます。
$DP[i]:=時間E_i$ までの幸福度の最大値
時間$E_i$までの幸福度としているのは、
$0 \le S_i \lt E_i \le 100000$
より、「時間$i$までの幸福度の最大値」としてしまうと状態数が多くなるからです。
(ここでは状態数を$(N=)3000$に抑えようとしています(後述))
次に、遷移の仕方について考えます。
ここでは配るDPを行うのですが、$dp[i]$から、視聴可能な映画を種類別に、同種類の映画を何個連続で見るか場合分けします。わかりにくいので入力例1で考えてみます。
4
100 200 300 400
1 0 120
1 15 135
2 10 40
1 240 330
まず、初期状態として、時間$0$の時の幸福度の最大値は0です。
ここから配るDPをします。
この場合、映画の種類は2種類存在しています。
type1 type2
| 開始時間 | 終了時間 | 開始時間 | 終了時間 | |
|---|---|---|---|---|
| 0 | 120 | 10 | 40 | |
| 15 | 135 | |||
| 240 | 330 |
ここで時間$0$直後から、type1またはtype2の映画を1回以上連続して視聴することを考えます。
例えば、type2を1回視聴すると幸福度は$(H[0]=)100$となります。
よって、$DP[0](\because E_0=40)$に幸福度100を配ります。
type1の連続視聴の回数は$0〜3$が可能性としてありますが、最適な視聴映画の選び方として貧欲法を使います。
具体的には、あらかじめ映画を終了時間で昇順にソートしておいた時に、終了時間の早い映画から順に、視聴できるならする、ということを繰り返します。これは、終了時間が早い映画を選んだ方が後に選択肢が残りやすい、と考えるとわかります。
この場合、
$0〜120$の映画を視聴する **」**ここまでで1つ視聴済み
$↓$
$15〜135$の映画は視聴できない
$↓$
$240〜330$の映画を視聴する **」**ここまでで2つ視聴済み
となります。
(これを全ての種類の映画について同様に行います)
よって、$dp[1](\because E_1=120)$に幸福度100を配り、
$dp[3](\because E_3=330)$に幸福度100+200を配る
と言うことを行えば良いです。
各$dp[i]$では最大値を取るようにします。
ここで、時間$E_i$から配る時に、「違う種類の映画を、混ぜて視聴する場合を考慮していない」と思うかもしれませんが、とりあえず連続して同種類の映画を視聴する場合のみに配れば、その配った先で、また別の種類の映画を視聴する場合に配ることになります。
こうすることで、連続して同種類の映画を視聴した時に生じる、幸福度の変化を一気に処理することができ(正確には累積和などを用いることで)、
DPの状態数$N$それぞれについて、
遷移に$O(N)$かかり、
合計で$O(N^2)$で解くことができます。
感想
青diffだったので、自力で解けてもよかったが、$O(N^3)$のDP解法しか思いつかなかった。
実装では、std::mapを用いることで少し簡略化できたが、無駄な部分も多いように感じた。
提出コード
参考になったら幸いです。