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$直後から、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を用いることで少し簡略化できたが、無駄な部分も多いように感じた。
提出コード

参考になったら幸いです。