bzoj 2654 && bzoj 3675 總結

手動博客搬家: 本文發表于20180929 15:18:55, 原地址https://blog.csdn.net/suncongbo/article/details/82897992

最近做到了兩道（我感覺）思路比較神的題，總結一下。
注：以下兩道題我都沒有用文中所述方法A過。

1. bzoj 2654

首先如果直接求MST，不能保證有恰好\(K\)條白邊。
而貪心顯然是錯的。
可以這樣想：如果題目里要求是恰好有\(0\)條白邊，我們可以讓所有白邊的代價增加\(+\inf\). 如果要求白邊最多，可以讓白邊代價增加\(-\inf\). 那既然這樣的話，MST中白邊的數量一定隨著給白邊增加的權值單調。因此可以二分，直到有\(K\)條白邊即可。最后答案減去\(K\times 增加的權值\).
好神啊www %%%cls
這道題非常重要，希望自己永遠也不要忘記這道題。

2. bzoj 3675

正解是斜率優化dp. 但這不是本文的重點。
如果只是斜率優化不搞點有意思的新東西也太無聊了吧！23333
從網上看到的神做法：
首先\(dp\)還是要的：假設\(dp[i]\)表示序列前\(i\)個數分割成若干段的最大得分，則枚舉最外層的一次劃分\(dp[i]=\max^{i}_{j=1} (s[i]-s[j])s[j]\), \(s[j]\)為權值的前綴和。但是這樣無法保證最優解能分成\(K\)段。行吧那我們假設\(dp\)方程長成了這樣: \(dp[i]=\max^{i}_{j=1} (s[i]-s[j])s[j]+C\), \(C\)為常數。顯然\(C \rightarrow +\inf\)時\(dp\)會自然而然地分成\(n\)段，反之\(C\rightarrow -\inf\)時會分成1段。因此可以二分\(C\), 當分的段數達到\(K\)時，就是答案。最后減去\(C\times K\).
這樣做應該是過不了的，但是至少能為我們提供一種思路。
如果在這個算法的基礎上加上斜率優化應該就差不多能過了，時間復雜度\(O(n\log W)\), \(W\)為值域。這樣\(K\)如果也是\(1e5\)應該也能過了。
（其實我是通過這題才看懂的上一題23333）

發表于 2019-01-22 19:47 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部

總結

以上是生活随笔為你收集整理的bzoj 2654 bzoj 3675 总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。