問題是﹕給了一個長度為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,需要用到滾動數組。
沒有留言:
張貼留言