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