POJ No.3276 Face The Right Way
3276 -- Face The Right Way
蟻本問題です.
左から牛を見ていき, 後ろを向いていた牛がいたらその牛を左端としたK個の区間の牛の前後をひっくり返し, 右へと見ていく. 左端からK個の区間がとれなくなるまで繰り返し, 残った区間の牛がすべて前を向いているかを確認し, 条件を満たしていればKを記録し, Mを更新する. Kを1~Nまで試して答え.
実装において, 牛をひっくり返すたびにBとFを交換していると面倒で, 計算量も大きくなります. そのために, 各要素についてその番号の牛を左端としたときにひっくり返す操作をしたかどうかを記録する配列を用意しておきます(ひっくり返したら1,ひっくり返していなかったら0).
i番目の要素を見ている時は, i-K+1~ i-1番目までの要素を何回ひっくりかえしたかがわかればi番目が今BかFか確定できます. いちいちi番目の要素をみるときにi-K+1~i-1番目を見ると, 計算量がかさみます. これを防ぐために, i-K+1~i-1 番目の和を格納する変数を用意しておき, iをインクリメントしたときにi-K+1番目の要素を引き, i-1番めの要素を足すしゃくとり和（？）をすることで定数時間でこの和を計算することができます.
