遷移の形は

\[dp[i]=\underset{0\leq j< i}{\min} \{ dp[j]+(i-j)\underset{j\leq l< i}{\max}c_l \} +a_i\]

となり、 \(O(N^2)\) 時間があれば解くことができます（もう一つの解説を参照してください）。この遷移を愚直に実装するとTLEになってしまいます。

この遷移を高速化するために、以下のような一次関数の集合を考えます。

\[S_i=\{dp[j]+(x-j)\underset{j\leq l\leq i}{\max}c_l \}_{j=0,1,\dots i}\]

これを用いると \(dp[i+1]=a_{i+1}+\min\{S_i(x=i+1)\}\) となります。また、 \(k < i\) の範囲で \(c_k > c_i\) となる最大の \(k\) (存在しなければ \(-1\) )を使って書き換えると、

\[S_i= S_k \cup \{ dp[j]+(x-j)c_i \}_{j=k+1,k+2,\dots i}\]

今、最小を求めたいので、右辺第2項は定数項が最小の1つ( \(l_i\) とする)のみを選べば良いです。定数項が最小の1つは

\[L_i=\{dp[j]-jx\}_{j=k+1,k+2,\dots i}\]

を用いて \(\min\{L_i|_{x=c_i}\}\) と書けます。 \(L_i\) は \(j \in (k,i]\) について一次関数 \(dp[j]-jx\) たちを集めたものなので、CHTをセグ木に載せると、傾きの単調性とクエリの単調性から、1回あたり償却 \(O(\log N)\) で求まります。

\(l_i\) が求まった時、 \(S_i\) は「 \(S_k\) の状態に直線 \(l_i\) を追加する」という操作を行えば良いです。これを実現するために、 \(i \rightarrow k\) の依存関係を木と見て、この木を HLD して、Heavy な辺のみからなるパス(chain)ごとにCHTを持つことにします。各 \(i\) における \(S_i\) を求めるためには、木を根の方に辿って最小を調べます。見るchainは \(O(\log N)\) 個で済むので、chainごとに \(x=i+1\) での最小を求めて、それらの最小を記録すればよいです。これによって、全体で \(O(N\log^2 N)\) になります。

また、 \(S_i\) を構成する時に \(S_k\) の状態に戻すという操作を行えば良いと考えて、永続Li Chao Treeなどのデータ構造によって操作を実現する方法もあるでしょう。