ABC209 F - Deforestation (600)
コンテスト中の考察
求めるのは最小になる場合の数
なので最小コストを求める必要がある
分からない
解説の解法
考察すると選び方によって変わるのは隣接する左右のどちらを先に取るのかだけ
高い方を先に取ると最小になる
挿入DPで解く
$ dp[i][j] で$ i番目まで見て$ i番を$ j番目に取る場合の数
$ dp[0][j] は$ j = 0で1、それ以外で0
1個しかないので当然最初に取る必要がある
他は以下のとおり
$ H_i = H_{i-1} なら$ dp[i][j] = \sum_{k=1}^{i} dp[i-1][k]
$ i番目を$ i-1番目の前にでも後にでも挿入できるため
$ H_i \gt H_{i-1} なら$ dp[i][j] = \sum_{k=j}^{i} dp[i-1][k]
$ i番目を$ i-1番目の後に挿入する必要があるので$ i-1は$ j番目以降である必要がある
$ H_i \lt H_{i-1} なら$ dp[i][j] = \sum_{k=1}^{j-1} dp[i-1][k]
$ i番目を$ i-1番目の前に挿入する必要があるので$ i-1は$ j-1番目以前である必要がある
愚直に和を取ると$ \mathcal{O}(N^3)になる
$ i 毎に$ r[j] = \sum_{k=1}^{j} dp[i-1][k] となるような累積和の配列$ rを求めておくと全体で$ \mathcal{O}(N^2)になる
$ r[j] = r[j-1] + dp[i-1][j-1] のように順に求める