測試資料(高中組初賽裁判測資)：http://contest.cc.ntu.edu.tw/npsc2009/schedule.htm
(NPSC2009高中組初賽pB)
有長度N<1000000的非負整數序列，
一段連續整數和代表一種出租方案的效能
也就是說有N(N+1)/2種不同的出租方案
問組合效能由小到大排列中排行第M的出租方案效能會是多少
程式碼(需要注意在ZeroJudge要改lld)：http://codepad.org/QHWc7dEA
當年只有4隊AC的題目
我是看著NPSC補完計畫照co作出來的
這裡試著給出比較詳細的解釋
--
設答案是M元可以租到效能K的方案
首先，如果「從價錢找答案」，從M到K的過程，勢必得把N(N+1)/2種方案全部搞出來
這樣不論空間或時間都是大大不夠的
換個角度想M和K的對應關係從俗語「一分錢一分貨」發現
效能K要花M元，那麼效能K-1(如果存在的話)要花的錢不可能比M還多
也就是這個函數呈單調非嚴格遞增
所以可以二分答案回頭檢查(也就是「從答案找要花多少錢」)
--
對於K最小可能是租最爛的電腦1台、最大是全部包下來進行二分搜尋
我們如何能算出對特定的效能K要花多少錢呢？
觀察看看，N(N+1)/2做了什麼不必要的事情
那就是假如租電腦1...10，那麼2...10、3...10、4...10、...等等
這些子區間的值全部都不會比原區間1...10還大！
(利用電腦的效能是「非負整數」這點)
所以想算出價錢(效能<=K的租賃方案數)，只要通盤考慮各種"最寬區間"[i,j)
列舉所有的j=1...N，queue裡面維護「最寬的[i,j)含有的元素們」、元素總合是sum
每一輪for都push一個元素到queue裡面，萬一sum太大，就從開頭pop掉(也就是i++)
並且對結尾是j的最寬區間進行可行方案數目的統計
--
舉例來說N=5，元素是1 2 1 3 5
我們想求解效能是9的方案應該要幾塊錢(也就是有多少方案的效能<=9)
j=1：[0,1)、sum=1、method+=j-i
只有租[0]這一種方法
j=2：[0,2)、sum=3、method+=2
租[0,1]如果可以的話，代表[1]當然也可以，方法數+2
j=3：[0,3)、sum=4、method+=3
這三種方法就是租[0,1,2]、[1,2]、[2]
j=4：[0,4)、sum=7、method+=4
租[0,1,2,3] [1,2,3] [2,3] [3]
j=5：這時候發現[0,5)總合是12，並不合乎效能<=9的要求，
所以開始pop掉元素，依次考慮[1,5)效能是11、[2,5)效能是9才又合乎要求
得到method+=3，[2,3,4]、[3,4]和[4]這三種
所以效能9要花1+2+3+4+3=13元
所有15種方案茲列表如下：
1
1
2
1 2
2 1
3
1 3
1 2 1
5
2 1 3
3 5
1 2 1 3
1 3 5
2 1 3 5
1 2 1 3 5
--
細節方面，需要考慮的是好比說效能3，可以是[1,2]、[3]或[2,1]，分別排行4,5,6
那意思就是說拿4塊錢、5塊錢、6塊錢都是租到效能3的電腦
(也就是二分搜尋在實作上要考慮到這類邊界，詳細請參考code)
-----
結論：
這個算法完全是基於各元素「沒有負數」所設計的
(檢查的部分)是赤裸裸鐵掙掙的線性算法
如果我們和經典DP問題「最大連續元素和(會有負的)」相互對照檢討變形一下
1.是否可以求出連續和第M大的方案？
2.是否可以求出次大連續元素和？
我有個思路是這樣的
把各段落>0的最大連續和求出來
試著從各段可能最大中構造出次大連續和
它們可能是：
(1)次大連續和剛好是DP中被忽略的某段不相交的和
ex: 1 2 3 4 5 -999 2 2 3 4 5
顯然最大和是後半，次大和是前半
(2)最大連續和扣掉頭或是扣掉尾巴(減少一個正數)
ex:1 2 3 4 5，試驗1 2 3 4和2 3 4 5發現2 3 4 5是答案
(3)最大連續和加上一個負數
ex: -1 2 3 4 6 2，最大和會是2 3 4 6 2，正確答案是加上一個負的變成-1 2 3 4 6 2
(4)最可怕的情形...加上一個正數、負數相間的段落
ex: -1 600 -450 600 -1050 4 50 6 700，最大和是4 5 6 700(刻意把中間有600卡掉)
但是次大和卻是最大和、把前面全部補進來(剛好是-1)
(同上，只要n^2就能解出來)
總結來說這讓我有兩個心得
A.所謂的經典DP問題，幾乎都是本質困難，
但是對特殊範圍、特殊構造、求特定解可以加以利用
(套句波利亞在「怎樣解題」上寫的，就是特殊化)
好比說帶負數的連續和問題，就特殊指名了「最大」
0-1背包問題也指名了背包容量V是個不太大的數字(也就是V到20億還是得暴搜)
狀態壓縮類的動態規劃也會透露它的求解域是狹長型的，好比說NOI砲兵陣地就是100*10
B.現實的應用問題很容易檢討的數字是正整數或非負整數
意即，走一條路花的時間不能是負(沒有時空隧道)
明明是買土地當然不會有買了還倒貼你錢這種事(價格是正的)
烤一片大小是x的pizza會花和x成正比的時間(沒有大小是負數的超時空pizza吧XD)
只要抓準一個問題的關鍵－找找單調性、試試看可不可以貪心、推敲一下子問題、…於是有效的算法就呼之欲出了
沒有留言:
張貼留言