bzoj1831【AHOI2008】逆序對
1831: [AHOI2008]逆序對
Time Limit:10 SecMemory Limit:64 MB
Submit:485Solved:341
[Submit][Status][Discuss]
Description
小可可和小卡卡想到Y島上旅游，但是他們不知道Y島有多遠。好在，他們找到一本古老的書，上面是這樣說的： 下面是N個正整數，每個都在1~K之間。如果有兩個數A和B，A在B左邊且A大於B，我們就稱這兩個數為一個“逆序對”。你數一數下面的數字裡有多少個逆序對，你就知道Y島離這裡的距離是多少千米了。 比如說，4 2 1 3 3裡面包含了5個逆序對：(4, 2), (4, 1), (4, 3), (4, 3), (2, 1)。 可惜的是，由於年代久遠，這些數字裡有一部分已經模糊不清了，為了方便記錄，小可可用“-1”表示它們。比如說，4 2 -1 -1 3 可能原來是4 2 1 3 3，也可能是4 2 4 4 3，也可能是別的樣子。 小可可希望知道，根據他們看清楚的這部分數字，能不能推斷出這些數字裡最少能有多少個逆序對。
Input
第一行兩個正整數N和K。第二行N個整數，每個都是-1或是一個在1~K之間的數。
Output
一個正整數，即這些數字裡最少的逆序對個數。
Sample Input
5 4
4 2 -1 -1 3
Sample Output
4
HINT
4 2 4 4 3中有4個逆序對。當然，也存在其它方案得到4個逆序對。
數據范圍：
100%的數據中，N<=10000，K<=100。
60%的數據中，N<=100。
40%的數據中，-1出現不超過兩次。
Source
Day1
動態規劃
首先，我們考慮填入的數需要滿足的性質。
對於兩個空位a和b，分別填入數x和y，且x
如果我們交換x和y，會有如下性質:
1.[1,a-1]和[b+1,n]中的數與x y構成的逆序對數不變。
2.[a+1,b-1]中大於x或小於y的數與x y構成的逆序對數不變。
3.[a+1,b-1]中在(x,y)范圍內的數與x y構成逆序對。
4.x y構成逆序對。
也就是說我們如果交換x y，逆序對數會增加。
所以填入的這些數一定是單調不減的。
有了這個性質我們就可以DP了。
用f[i][j]表示第i個空位填j所形成的最小逆序對，g[i][j]表示f[i][1]-f[i][j]的最小值，cost[i][j]表示在第i個空位填j所形成的新的逆序對。顯然cost[i][j]是可以預處理的。
則f[i][j]=g[i-1][j]+cost[i][j]。
注意最終答案還要加上不是空位的數形成的逆序對數。
(感覺自己表達能力好差......看不懂的話還是看代碼吧...QAQ)
