Codeforces #13 C Sequence

問題是﹕給了一個長度為N的整數數列A，1 <= N <= 5000，每次操作可以把數列內任意一個數+1或-1，求最少操作使得該數列是單調遞增的。

試了一次貪心的方法，結果不行。後來轉為動態規劃。

Observation 1: 目標數列只會取值原本數列內的數。即數列A內含{1, 3, 5, 7, 8}，那麼經最少操作後的數列都只包含{1, 3, 5, 7, 8}的子集。

有了這樣的想法之後，簡單的動態規劃轉移方程可以這樣寫﹕
定義﹕
F(i, j): 把數列內首i個數用最少操作，成為單調遞增序列的操作數量，且第i位數取值B[j]。
B: 把數列A按遞增排序。

F(0, j) = |A[0] - B[j]|
F(i, j) = min{F(i-1, k) + |A[i]-B[j]| | 1 <= k < j} = min{F(i-1, k): 1<=k < j} + |A[i]-B[j]|

由於計算F(i, j)時順道update min{F(i-1, k): 1<=k < j}，因此整個算法是O(N^2)。留意N最多5000而Memory只有64MB，需要用到滾動數組。