P6944 [ICPC2018 WF]Gem Island

之前一直都沒有弄懂pht轉(zhuǎn)化有什么用，現(xiàn)在懂了，故作文以記之。

直接從CYJ的題解開始講起，這種階梯DP是人都想得出來，只不過是 \(O(n^4)\) 或者 \(O(n^3ln (n))\) 的，本人覺得這道題的關(guān)鍵在于如何優(yōu)化掉整整一個 \(O(n)\)
首先一個數(shù)列的權(quán)值就是類似于 \(\sum i*cnt(i)\) 的，先進行一步pht轉(zhuǎn)化得到 \(\sum cnt(x\ge i)\)。
這種轉(zhuǎn)化的意義在于把每一層的區(qū)別給打破了，意思就是可以若干層一起轉(zhuǎn)移：
假如沒有進行pht轉(zhuǎn)化，那么在做DP的時候我們顯然要先枚舉那個 \(i\) ，這樣就把每一層給徹底區(qū)分開來，就無法優(yōu)化了，但是如果進行pht轉(zhuǎn)化后，每一層的轉(zhuǎn)移的貢獻就只與這一層放了多少個元素有關(guān)而與這是第幾層無關(guān)，因此我就可以把枚舉層數(shù)的那一維給省去了，而在轉(zhuǎn)移的過程中則就是把一堆雖然轉(zhuǎn)移的層數(shù)不同但是轉(zhuǎn)移的那層放的元素的個數(shù)相等的一坨狀態(tài)一起轉(zhuǎn)移，而計算的方向也就是 \(d\) 單調(diào)遞增，我認為這個轉(zhuǎn)化是非常巧妙的。
歸納可以使用pht轉(zhuǎn)化：
① \(ans=\sum i*cnt(i)\)
② 一般都是有多個狀態(tài)，在轉(zhuǎn)化之后也就是優(yōu)化掉某個狀態(tài)之后仍然具有轉(zhuǎn)移的方向

UPD on 20241115: 其實 pht轉(zhuǎn)化 的原名叫做 阿貝爾變換 ，不過是 pht 教我的，所以就叫做 pht轉(zhuǎn)化 啦