PKU3670-Eating Together

題目：http://poj.org/problem?id=3670
由N(30000)個{1,2,3}組成的數列，每次可以塗掉一個號碼換任意一個新的號碼
問最少要塗改幾次才能把整個數列弄成不遞增或不遞降


程式碼：http://codepad.org/yqTzvpCH
<只要把"不遞降"部分留下，就能直接AC掉PKU3671-Dining Cows>

做法一：O(n)
由於數列組成集只有1,2,3三種可能性
定義狀態DP[n][i]代表當前n個數不遞降，並且第n個數是i時所需的塗改成本
於是轉移就很容易想、不遞增反過來再做一遍就行

做法二：O(nlgn)
把LIS求出來，然後N-LIS長度就是答案