sankantsuのブログ

技術メモ・競プロなど

ABC251 E - Takahashi and Animals 解説

競プロ

以下の $N$ 個の行動がある．

行動 $1$ : 動物 $1$ と動物 $2$ に $A_1$ 円で餌をあげる
行動 $2$ : 動物 $2$ と動物 $3$ に $A_2$ 円で餌をあげる

$\vdots$
行動 $N$ : 動物 $N$ と動物 $1$ に $A_N$ 円で餌をあげる

すべての動物に餌をあげるための最小コストを計算したい．

少し観察すると，次の特徴がわかる．

動物 $i$ に餌をあげるためには，行動 $i\mathord-1$ か行動 $i$ の少なくとも一方は行う必要がある．

したがって，まず動物 $1$ に対して行動 $1$ か行動 $N$ のどちらかによって餌を与えるか決め，さらに動物 $2$ , $3$ と順に餌を与える方法を決めていく動的計画法で解けそうとわかる．

$dp[0] [j]$ : 行動 $N$ を使って $1,\ldots,j$ 番目の動物に餌を与えるための最小コスト
$dp[1] [j]$ : 行動 $N$ を使わずに $1,\ldots,j$ 番目の動物に餌を与えるための最小コスト

と定める．

動物 $j$ に餌を与える方法は行動 $j\mathord-1$ か行動 $j$ のいずれかであるから，

$\displaystyle dp [i] [j] = \min \{ dp [i] [j-2] + A[j-1] ,\, dp[i] [j-1] + A[j] \}$

によって求められる．

行動 $0$ を使っていた場合にはすでに動物 $N$ には餌を与えているので， $dp [0] [N-1]$ と $dp [1] [N]$ の小さいほうが答えである．

実装例

文章の説明と添字がずれているのと，テーブルの更新順が若干違うことに注意．