Re: [心得] Maximum sum k-disjoint subarrays

看板Prob_Solve (計算數學 Problem Solving)作者 (喔喔)時間3年前 (2021/02/18 13:46), 編輯推噓0(000)
留言0則, 0人參與, 最新討論串2/2 (看更多)
※ 引述《FRAXIS (喔喔)》之銘言: : 題目:給定一含有 n 個整數的陣列 A ,找出不相交的 k 個子陣列其總和最大。 : 也就是要找 k 組索引對 (b1, e1), ... (bk, ek), bi < ei 且 ei < b_{i+1} : 使得 A[bi...ei] 的總和最大。 最近有人跟我說這一題有另一種想法,所以跟大家分享一下。 可以參考這個網站: http://www.serbanology.com/article/The%20Trick%20From%20Aliens 解題的技巧叫做 Alien's Trick (IOI 2016 的 Aliens 題)或是 WQS binary search。 簡單來說,如果 A 是給定,我們令 f(x) 為 不相交 x 個子陣列最大的總和 (此時 x 是變量,雖然我們只想算 f(k))。 然後引入 Lagrange multiplier λ,計算 L(x, λ) = f(x) - λx。 可以想像 λ 是建立一個新子陣列的 penalty 。 (我其實看不太出來這跟 Lagrange multiplier 有甚麼關係,雖然函數很像,但是 Lagrange multiplier 主要是在處理連續的函數而不是離散函數) 此時我們會發現 λ 增加時,argmin_x L(x, λ) 會減少。 當 λ 是 0 時,因為建立子陣列的 penalty = 0,就是挑 A 中所有的正數,每一個正數 是一個獨立的子陣列。 當 λ 很大時,就會挑比較少子陣列。 想法就是 binary search λ,直到 argmin_x L(x, λ) = k 為止, 而 argmin_x L(x, λ) 可以用 DP 在線性時間內算出。 λ 一般都可以找出合理的上限 U,所以不會時間複雜度可以是 O(n lg U)。 (真要分析的話,只需要考慮 λ = A[i..j] 總和的情況, 因為 i, j 只有 O(n^2) 組合,而且可以藉由建構 prefix sum array 的方式計算 子陣列總和,所以應該 O(n lg n) 算法是可行的) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47 (美國) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1613627212.A.145.html
文章代碼(AID): #1WBVzC55 (Prob_Solve)
討論串 (同標題文章)
文章代碼(AID): #1WBVzC55 (Prob_Solve)