AOJ 2900 - 凸凹数列

問題
提出コード

解法

半分ぐらい貪欲です。
前から貪欲に、凹凸がズレていたら操作、ということを行うだけで条件を満たす数列を作成できます。
なので、最大でも数字の個数分の回数しか操作を行うことはありません。
ということで、基本的には貪欲に操作を行っていきます。
コーナーケースとなるのが、
1 3 4 2
のように数字が並んでいるケースで、これは3と4をスワップすると、2と3の辻褄が合わなくなるので操作回数が2回になりますが、実は4と2をスワップすることで操作回数を1回に抑えることができます。
なので、このようなパターンだけ、分岐をして調べればいいでしょう。
ということで、あとはこれを再帰して調べることで答えが求まります。
分岐するパターンはそこまで多くないので、メモ化をする必要もとくにありません。
凹凸凹凸…となるパターンと、凸凹凸凹…となる2つのパターンについて調べることを忘れないようにすれば、最小値が求まるはずです。