討論串[問題] Reduce LP成Min-cost flow
共 5 篇文章
內容預覽:
在網路上看到一個問題：. 給定一個整數陣列 A ，一個正整數D，要求設計一個演算法把. A 修改成 B （長度不變），使得 B 中相鄰的元素的差值都小於D，. 且最小化 |A[i] - B[i]| 的總和。. http://www.careercup.com/question?id=52071971
(還有171個字)
內容預覽:
竟然會有 FRAXIS 也納悶求解的問題？！. 這引起了我的注意。. 完全不想點擊連結：因為我相信 FRAXIS 有看懂問題且敘述為真。. 而我也看仔細了中文問題描述。. 那麼，我就在不使用 Linear Programming、網路流 這兩類演算法的限制下，. 此時刻開始進行解題，用自己的方法(其
(還有236個字)
內容預覽:
我知道LP不可能都可以換成min-cost flow，因為min-cost flow是LP的特例。. 但是在某些情況下，先設計好LP，然後就可以系統化的轉換成min-cost，. 這會比直接設計min-cost來的容易一些。. 比如說這一題：. https://www.byvoid.com/blog
(還有536個字)
內容預覽:
我也看不太懂，我猜是這樣：. 令a[i]=h[i]-h[i+1]. h[i]加1 <=> a[i-1]減1 且 a[i]加1。. h[i]減1 <=> a[i-1]加1 且 a[i]減1。. h[i]加1，可以視作「一單位的水從a[i-1]流到a[i]」。. h[i]減1，可以視作「一單位的水從a[
(還有499個字)
內容預覽:
我好像大概了解了，不知道有沒有錯... 輸入為A，然後前處理計算P[i] = A[i] - A[i+1]，我們要求解B[]。. 令 X[i] 為變數表示 A[i] 的增加量。. Y[i] 為變數表示 A[i] 的減少量。. 所以 B[i] = A[i] + X[i] - Y[i]，目標是要極小化X[
(還有587個字)