yukicoder 1438 Broken Drawers
連続単調減少列ごとに分けて考える. ある連続単調減少列の長さが
$ K
のとき, 答えには
$ \lfloor \frac{K}{2} \rfloor
を足せばよい. これをすべての連続単調減少列について計算し, その和を
$ S
とすると
$ N - S
が答えとなる.
実装例:
https://yukicoder.me/submissions/634282