どのような順番で木を伐採していくとコストの総和が最小になるのでしょうか？

まず、各木の高さが最終的なコストの総和にどのくらい寄与しているのかを考えます。この発想は主客転倒と呼ばれるテクニックで、競技プログラミングにおいてよく使われます。

木 \(i\) の高さ \(H_i\) について、

• 木 \(i+1\) を切るときにコストに寄与する回数を \(A_i\)
• 木 \(i\) を切るときにコストに寄与する回数を \(B_i\)
• 木 \(i-1\) を切るときにコストに寄与する回数を\( C_i\)

とします。すると、\(B_i\) は木を切る順番によらず ​\(1\) です。 \(A_i\) は、木 \(i\) より木 \(i+1\) を先に切った場合 \(1\)、そうでないなら \(0\) です。 \(C_i\) は、木 \(i\) より木 \(i-1\) を先に切った場合 \(1\)、そうでないなら \(0\) です。

すなわち、各 \(i\,(1 \leq i \leq N-1)\) について、

• 木 \(i\) より木 \(i+1\) を先に切った場合 \(H_{i}\)、そうでないなら \(H_{i+1}\)

がコストに加算されます。

以上のことから、コストが最小となるための木を伐採する順番の条件は

• \(H_i < H_{i+1}\) ならば木 \(i+1\) を木 \(i\) よりも先に伐採する
• \(H_i > H_{i+1}\) ならば木 \(i\) を木 \(i+1\) よりも先に伐採する

が全ての \(i\,(1 \leq i \leq N-1)\) に対して成り立つことです。

次にこの条件を満たす木を伐採する順番の総数の求め方について解説します。これは、以下のような DP を考えるとよいです。

• \(dp_{i,j}=\,(\)番号が \(i\) 以下の木を全て伐採する方法で、木 \(i\) が \(j\) 番目に伐採されるようなものの総数\()\)

遷移は以下のようになります。

• \(H_i=H_{i+1}\) のとき、\(dp_{i+1,j}= \sum_{k=1}^{i} dp_{i,k}\)
• \(H_i<H_{i+1}\) のとき、\(dp_{i+1,j}= \sum_{k=j}^{i} dp_{i,k}\)
• \(H_i>H_{i+1}\) のとき、\(dp_{i+1,j}= \sum_{k=1}^{j-1} dp_{i,k}\)

愚直に遷移すると \(Θ(N^3)\) かかってしまいますが、累積和を用いて高速化することで \(O(N^2)\) で解くことができます。このように、要素を挿入していく DP の組み方は一般に挿入 DP と呼ばれます。

類題：https://atcoder.jp/contests/dp/tasks/dp_t