「みんなのプロコン 2019」：D - Ears
問題
解法
dpR1(i) := 座標 i にいて，これから右に行き座標 i に戻ってこないとき，i 番目の耳以降操作しなければいけない回数の最小値
dpR2(i) := 座標 i にいて，これから右に行き座標 i に戻ってくるとき，i 番目の耳以降操作しなければいけない回数の最小値
dpL1(i) := 座標 i にいて，これから左に行き座標 i に戻ってこないとき，i - 1 番目の耳以降操作しなければいけない回数の最小値
dpL2(i) := 座標 i にいて，これから左に行き座標 i に戻ってくるとき，i - 1 番目の耳以降操作しなければいけない回数の最小値
と DP を定義する．このとき，dpR2 と dpL2 の更新は座標 i より先に移動するかどうかの二つの選択肢があり，dpR1 と dpR2 の更新は座標 i の隣に戻らず先に進むか，座標 i の隣に戻ってくるように先に進むか，これより先に進まないかの三つの選択肢がある．それぞれ A_i や A_(i - 1) が 0 であるかや偶奇によって次の座標に進むときにかかるコストが加算される（詳しくはコード参照）．答えは，散歩を開始する座標を全て試す．開始する座標を決めたら，「左へ行き，戻ってきて，右へ行き，そのまま戻ってこない」「右へ行き，戻ってきて，左へ行き，そのまま戻ってこない」「左へ行き，戻ってきて，右へ行き，戻ってくる」の三つの行動のうち最も回数が少ないものをその開始する座標における答えとすればよい．あとはこれらの最小値を取ればよい．O(L)．
解答
