這道NOIP2005的題目是道好題，思路多多，編碼技巧多多。據(jù)說(shuō)NOI夏令營(yíng)的時(shí)候虎爺
還專門拿出來(lái)津津樂(lè)道（汗~）。 鑒于好久沒(méi)做NOI的題了，正巧有人問(wèn)道，就寫個(gè)解題報(bào)
告吧。
題目描述
在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石
子，青蛙很討厭踩在這些石子上。由于橋的長(zhǎng)度和青蛙一次跳過(guò)的距離都是正整數(shù)，我們可
以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，……，L（其中L是橋的長(zhǎng)度）。
坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L(zhǎng)的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)
方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過(guò)坐標(biāo)為L(zhǎng)
的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。
題目給出獨(dú)木橋的長(zhǎng)度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定
青蛙要想過(guò)河，最少需要踩到的石子數(shù)。
對(duì)于全部的數(shù)據(jù)，L <= 10^9。
輸入格式
輸入的第一行有一個(gè)正整數(shù)L（1 <= L <= 10^9），表示獨(dú)木橋的長(zhǎng)度。第二行有三個(gè)
正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中
1 <= S <= T <= 10，1 <= M <= 100。第三行有M個(gè)不同的正整數(shù)分別表示這M個(gè)石子在數(shù)
軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒(méi)有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開。
輸出格式
輸出只包括一個(gè)整數(shù)，表示青蛙過(guò)河最少需要踩到的石子數(shù)。
樣例輸入
10
2 3 5
2 3 5 6 7
樣例輸出
2
分析：
首先注意下數(shù)據(jù)量，maxL=10^9，這是一個(gè)即使是線性算法也已經(jīng)逼近運(yùn)行時(shí)限的規(guī)模。
所以要準(zhǔn)備好進(jìn)行極限優(yōu)化。
顯而易見(jiàn)，最純樸的想法是嘗試搜索，從一個(gè)點(diǎn)擴(kuò)展出所有可能跳到的點(diǎn)，依此類推，
最后DFS尋找由頂至下經(jīng)過(guò)石子最少的路徑即可。但注意到樹的寬度有可能達(dá)到maxJump=10，
深度也和L成正比，故蠻力搜索不現(xiàn)實(shí)。
可不可以進(jìn)行優(yōu)化呢？我們注意到，DFS效率低下的一個(gè)很重要原因是，遞歸遍歷的路
徑有許多次其實(shí)是同一條路徑，這些重復(fù)工作消耗了太多時(shí)間。于是我們自然而然想到要尋
找記憶化的算法。
我們發(fā)現(xiàn)，這個(gè)問(wèn)題實(shí)際上包含最優(yōu)子結(jié)構(gòu)，只要青蛙能站在某一個(gè)位置，以它的智商
絕對(duì)會(huì)從前面k個(gè)可能的位置中，尋找這么一個(gè)位置，這個(gè)位置所處在的跳躍路徑上所經(jīng)過(guò)的
石子是最少的，從這個(gè)位置跳躍而來(lái)。顯然，這個(gè)性質(zhì)是遞歸定義的。 額外的，我們看到，
當(dāng)青蛙站在某條路徑上的某個(gè)位置，那么它此后跳躍的路徑（當(dāng)然是可能的路徑）的選擇并
不受之前的結(jié)果所干涉，因此問(wèn)題具備無(wú)后效性。
可以動(dòng)規(guī)了，下面直接給出轉(zhuǎn)移方程。
DP[n]=min{DP[k]|n-maxJump<=k<=n-minJump}+t
t=0||t=1
即，設(shè)一個(gè)位置可以到達(dá)，那么必從前面可能的位置選擇一個(gè)，該位置所處的路徑上經(jīng)
過(guò)石子最少。若當(dāng)前位置有石子，dp結(jié)果再加一。
這是一個(gè)O(n)的順推，但是，如果minJump-maxJump=1-10，常數(shù)C就會(huì)太大造成超時(shí)。能
不能再優(yōu)化呢？仔細(xì)觀察，發(fā)現(xiàn)石子最多有100粒，在整個(gè)10^9長(zhǎng)度中分布相當(dāng)稀疏，這是一
個(gè)很重要的特點(diǎn)！假設(shè) minJuump!=maxJump，那么若空白位置足夠長(zhǎng)，dp的結(jié)果最終都會(huì)趨
向于一個(gè)穩(wěn)定值，這個(gè)值是前面所有可能的dp結(jié)果中最小的那個(gè)(請(qǐng)讀者自己想象，若跳躍的
步長(zhǎng)可以選擇，即跳到某個(gè)位置的起跳點(diǎn)可以選擇的話，在足夠遠(yuǎn)的未來(lái)，一個(gè)聰明的青蛙
肯定會(huì)在一條最優(yōu)的路徑上屁顛著~ 汗)。
例如在這一數(shù)據(jù)
25
4 5 5
2 3 5 6 7
0~4位置的初始dp指依次為 [0,0,1,1,0]，它將有如下變化，并且趨于穩(wěn)定值0：
(0~5)=[0,0,1,1,0,1]
(1~6)=[0,1,1,0,1,1]
(2~7)=[1,1,0,1,1,1]
(3~8)=[1,0,1,1,1,0]
(4~9)=[0,1,1,1,0,0]
(5~10)=[1,1,1,0,0,2]
(6~11)=[1,1,0,0,2,2]
(7~12)=[1,0,0,2,2,0]
(8~13)=[0,0,2,2,0,0]
(9~14)=[0,2,2,0,0,0]
(10~15)=[2,2,0,0,0,2]
(11~16)=[2,0,0,0,2,0]
(12~17)=[0,0,0,2,0,0]
(13~18)=[0,0,2,0,0,0]
(14~19)=[0,2,0,0,0,0]
(15~20)=[2,0,0,0,0,0]
......
為了利用這個(gè)性質(zhì)，我們先確定要使用的數(shù)據(jù)結(jié)構(gòu)。顯而易見(jiàn)的，對(duì)第i個(gè)位置的計(jì)算，
只依賴于距離i一定距離的數(shù)個(gè)已知結(jié)果。因此，我們只需關(guān)心相對(duì)坐標(biāo)即可，于是使用隊(duì)列
保存i之前一定距離內(nèi)的dp結(jié)果，計(jì)算完畢后 dp[i-maxJump] 出隊(duì)，dp[i]入隊(duì)，再利用該隊(duì)
列計(jì)算dp[i+1]，如此往復(fù)循環(huán)。
現(xiàn)在回到之前的討論，當(dāng)一個(gè)隊(duì)列中的結(jié)果已經(jīng)達(dá)到穩(wěn)態(tài)，那么對(duì)下一次計(jì)算，它只能產(chǎn)
生兩種結(jié)果：如果計(jì)算位置沒(méi)有石子，那么隊(duì)列仍然保持穩(wěn)定；如果有石子，那么加一的結(jié)果
將使得隊(duì)列再次出現(xiàn)不穩(wěn)定。 多么令人振奮的結(jié)論！
這意味著什么呢？這意味著當(dāng)你發(fā)現(xiàn)隊(duì)列已經(jīng)進(jìn)入穩(wěn)定的時(shí)候，后面所有對(duì)不存在石子的
位置進(jìn)行的計(jì)算都是可以忽略的，你不妨直接計(jì)算到下一個(gè)未訪問(wèn)的且有石子的位置即可。
很多人已經(jīng)看到了，這是一個(gè)狀態(tài)壓縮+DP的做法。
算法終止: 1.dp已計(jì)算完所有石子并且結(jié)果進(jìn)入穩(wěn)定態(tài)
2. 隊(duì)列已經(jīng)穩(wěn)定并且下一個(gè)落地的位置所有可能的起點(diǎn)都在橋的終點(diǎn)或之外
讀者可以自行分析中止的條件，剩下的只需要考慮細(xì)節(jié)問(wèn)題就可以了，只要思路清晰本
題就不會(huì)太難過(guò)。算法的實(shí)際運(yùn)行效率沒(méi)有問(wèn)題，單個(gè)極限數(shù)據(jù)只消耗了45ms。
本題據(jù)說(shuō)還有其他解法，例如數(shù)學(xué)觀點(diǎn)、最短路觀點(diǎn)等，感興趣的可以google下。
下面給出算法的main函數(shù)框架.
int main(){
scanf("%d%d%d%d",&l,&s,&t,&m);
for(step=0;step<m;step++)
scanf("%d",&stone[step]);
qsort(stone,m,sizeof(stone[0]),cmp);
_que=(Queue)CreatNewQueue;
for(step=0;step<t;step++) Enqueue(_que,0); //初始化DP隊(duì)列
result=0;
stepTotal=0;
stepStone=-1;
if(s!=t){
while(1){
if(IsStran(_que)){
if(stepTotal-t>=l||stepStone==m-1) break;
stepStone++;
stepTotal=stone[stepStone];
}
else
stepTotal++;
DPCompute(_que,stepTotal,stone);
}
result=_que->head->dpS;
}
else{
// 當(dāng)s=t 時(shí)其實(shí)仍然符合轉(zhuǎn)移方程的定義，但簡(jiǎn)單起見(jiàn)寫成了如下形式
for(step=0;step<m;step++)
if(stone[step]%s==0) result++;
}
printf("%d\n",result);
return 0;
}