李宇亮-神奇的K線

《李宇亮-神奇的K線》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、神奇的K線【算法分析】假設(shè)給出的序列是a。對(duì)于每個(gè)a[i]有3種決策，刪除它、保留它或者修改它。很容易想到DP。可以先確定一個(gè)大致的狀態(tài)為f[i][j]，含義為將a中前i個(gè)元素通過(guò)一系列操作對(duì)應(yīng)到新序列中的前j個(gè)元素的最小代價(jià)。但是這有一個(gè)問(wèn)題，無(wú)法確定新序列中第j個(gè)元素的確切值。一種解決方案是給狀態(tài)添加一維。算法1：DP，狀態(tài)f[i][j][k]表示原序列的前i個(gè)對(duì)應(yīng)于新序列的前j個(gè)，并且新序列的第j個(gè)數(shù)是k。轉(zhuǎn)移方程f[i][j][k]=min{f[i-1][j-1][k-p[j-1]](若a[i]=

2、k)，f[i-1][j-1][k-p[j-1]]+modify，f[i-1][j][k]+delete}。2時(shí)間復(fù)雜度O(nmax)，max表示數(shù)列可能的最大值。期望得分10~40。另一種解決方案是修改f[i][j]的含義，規(guī)定a中第i個(gè)元素被保留，得到新序列中第j個(gè)元素的最小代價(jià)。算法2：DP，狀態(tài)f[i][j]（j≤i）表示新序列中保留a[i]，并且a[i]是新序列中的第j個(gè)元素的最小代價(jià)。狀態(tài)轉(zhuǎn)移：f[i][j]=min{f[i’][j’]+modify*(j-1-j’)+delete*((i-j)

3、-(i’-j’))}，其中j’

4、P，狀態(tài)f[i][j]（j≤i）表示新序列中保留a[i]，并且a[i]是新序列中的第j個(gè)元素的情況下，原序列中最多能保留多少個(gè)元素。狀態(tài)轉(zhuǎn)移：f[i][j]=max{f[i’][j’]+1}，j?1其中j’

5、新序列中是第j個(gè)元素，那么新序列j?1中的第一個(gè)元素就是a[i]??p[k]，設(shè)為first[i][j]。k?1由于轉(zhuǎn)移只發(fā)生在first相等的狀態(tài)之間，據(jù)此可以得到算法4。算法4：將first不同的狀態(tài)分開(kāi)計(jì)算。這樣在尋找前繼狀態(tài)時(shí)就不會(huì)找到大量first[i’][j’]≠first[i][j]的狀態(tài)了。在first中的每種數(shù)個(gè)數(shù)都不多時(shí)效果較好。時(shí)間4復(fù)雜度O(n)，期望得分30~60。將f列成一個(gè)表格：j1234567i1234567圖中灰色格子的狀態(tài)是無(wú)用的。藍(lán)色格子代表狀態(tài)f[i][j]，能轉(zhuǎn)移

6、到它的狀態(tài)在紅色區(qū)域中，可以發(fā)現(xiàn)紅色格子組成一個(gè)平行四邊形。據(jù)此，我們可以得到兩種算法：算法5：還是將first不同的狀態(tài)分開(kāi)計(jì)算。按照優(yōu)先(i-j)從小到大，(i-j)相同則j從小到大的順序dp。這樣在計(jì)算f[i][j]（藍(lán)色格子）時(shí)，所有的前繼狀態(tài)（紅色格子）都已經(jīng)被算出，并且第j’列中已經(jīng)被計(jì)算的狀態(tài)f[i’][j’]都滿足i’-j’≤i-j。對(duì)于同一列中已經(jīng)被計(jì)算的狀態(tài)，只需要保存最優(yōu)的那個(gè)即可。這樣在計(jì)算一個(gè)狀態(tài)f[i][j]時(shí)，只需要掃一遍1~(j-1)列中的最優(yōu)狀態(tài)，取其中最優(yōu)的即可；計(jì)算好

7、地f[i][j]后，再用它更新第j列的最優(yōu)狀態(tài)。這樣轉(zhuǎn)移的復(fù)雜度降為O(n)，總時(shí)間復(fù)3雜度降為O(n)，期望得分60。由于每次轉(zhuǎn)移要找的列是1~(j-1)列，是連續(xù)的，所以可以用線段樹(shù)來(lái)維護(hù)連續(xù)列2的最優(yōu)狀態(tài)。轉(zhuǎn)移復(fù)雜度就降為O(logn)，總時(shí)間復(fù)雜度降為O(nlogn)，期望得分100。標(biāo)程用的是這種算法。算法6：類似于算法5，不過(guò)按照優(yōu)先j從小到大，j相同則i從大到小的順序dp。定義斜線k為所有i-j=k的狀態(tài)f[i][j]組成的狀態(tài)集合。線段樹(shù)維護(hù)的是每一條斜線上的最優(yōu)狀態(tài)。計(jì)算狀態(tài)f[i][j

8、]時(shí)，只需要用斜線1~(i-j)中的最優(yōu)狀態(tài)來(lái)轉(zhuǎn)移即2可。時(shí)間復(fù)雜度O(nlogn)，期望得分100。為什么還要將first不同的分開(kāi)呢？因?yàn)槿绻黄鹱觯敲磳?duì)于每一個(gè)first都要開(kāi)一個(gè)數(shù)組來(lái)記錄最優(yōu)狀態(tài)，空間不夠。其實(shí)還可以將狀態(tài)f[i][j]的含義改為前(i+j)個(gè)，刪除i個(gè)，留下（保留或修改）j個(gè)，并且第(i+j)個(gè)保留。這樣轉(zhuǎn)移的區(qū)域就從一個(gè)非矩形的平行四邊形變成了一個(gè)矩形（如下圖）。雖然和前面的狀態(tài)是等價(jià)的，但是更