ABC209 F - Deforestation - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

長さ ${N}$ の数列 ${H}$ に対して以下の操作を行うことで ${H}$ の任意の要素を ${0}$ にするときのコストが最小となるような操作列の数を求めよ．

${1\leq i\leq N}$ を選び ${H_i}$ を ${0}$ にする．このとき，この操作を行う前の ${H_{i-1}+H_i+H_{i+1}}$ 分だけコストがかかる．

また， ${H_0=H_{N+1}=0}$ とする．

${0\leq N\leq 4000\\ 1\leq H_i\leq 10^9}$

解説

${H_i}$ の大きい方から取っていくのがよさそう．実際， ${H_i}$ の降順に操作を行えば最小コストになる．ただし， ${H=\{4,2,3\}}$ とかだったら ${3}$ から操作をしてもいい．結局大事なのは隣り合う要素の大小関係で，

${H_i < H_{i+1}}$ なら ${H_{i+1}}$ から操作を行う．
${H_i > H_{i+1}}$ なら ${H_i}$ から操作を行う．
${H_i=H_{i+1}}$ ならどちらから行ってもいい．

という条件を満たすような操作列を数え上げたい．(適当に有向辺を張ったグラフのトポロジカルソートの数え上げのようなもの)

${i}$ の昇順に ${H_i}$ を左から並べていく(左のものから操作する)．ここでは例として ${H=\{3,1,4,1,5\}}$ を考える．

f:id:kanpurin:20210710225848p:plain:w300

まず， ${H_1=3}$ を置く．

f:id:kanpurin:20210710230818p:plain:w300

次に ${H_2=1}$ を置きたいが， ${H_1 > H_2}$ であるため ${H_1}$ の右側に置くしかない．この場合並べ方は次の ${1}$ 通り．

f:id:kanpurin:20210710230901p:plain:w300

次の ${H_3=4}$ は ${H_2 < H_3}$ であるため ${H_2}$ の左側に置く．置き方は次の2通り．

f:id:kanpurin:20210710231019p:plain:w300

残りも同様に ${H_3 > H_4}$ なので ${H_4}$ は ${H_3}$ の右側， ${H_4 < H_5}$ なので ${H_5}$ は ${H_4}$ の左側という風においていけばいい．

ここで重要になるのが，ある要素 ${H_i}$ を置く方法の数を求めるのに必要なのが ${H_{i-1}}$ が今まで並べた ${i-1}$ 要素のうち左から何番目に置かれているかという情報のみであるということ．これを状態として持ちながらDPできる．

${dp[i][j]}$ を「 ${H_i}$ まで並べて， ${H_i}$ が ${j}$ 番目にあるような並べ方の数」とすると遷移は以下の様になる．

$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]　(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})$ の遷移について説明する．
既に ${H_i}$ まで並べられている列の ${j}$ 番目に ${H_{i+1}}$ を入れる．

f:id:kanpurin:20210710234653p:plain:w400

このとき， ${H_{i+1}}$ を入れた後に「 ${H_i}$ より ${H_{i+1}}$ が左に置かれている」という条件が成り立つ必要があり，これが成り立っているようなものは ${H_i}$ が ${j}$ 番目から ${i}$ 番目にある列であるので， ${dp[i+1][j]}$ には ${dp[i][k](j\leq k\leq i)}$ からの遷移がある．