設f(i)代表至少到達坐標I時踩過的石頭數。
R(i)表示坐標I上是否有石頭，如果有石頭，r(i)=1，否則r(i)=0。
F(i)=min{f(j)}+r(i)，其中s
邊界f(0)=0
Ans=min{f(i)}，其中I >；=L
該算法的時間復雜度為O(L*(t-s))。
深度分析:
直觀來說，我們沒有必要對壹個沒有石頭的大區域進行動態規劃。
可以證明，當空白區域大於某個max時，青蛙壹定可以從區域的壹端跳到另壹端。
事實上，對於跳躍間隔[s，t]，max
所以我們可以把每段的長度>:max的空白區域壓縮到max的長度。這樣，總的L '只有m * max
這樣，前面的動態規劃的復雜度為O(L'*(t-s))，在限定的時間內可以得到解。
這個分析是NOIP2005唯壹獲獎者(保送北大)姚金玉給出的:長沙雅禮中學。
【問題分析】
乍壹看，這個問題是壹個典型的搜索問題。從河的壹邊到另壹邊，找到可以踩的最少的石頭。但是從數據範圍來看。1 ...109橋長。即使是O(n)算法也無法在壹秒鐘內解出答案。
如果搜索石頭，方法就比較難了。這個要考慮到前後連續的石頭。換壹種方式。利用動態規劃，具有分階段石頭的壹維動態量規的時間復雜度為O(n2)。最多只有100×100的時間。但是這樣劃分狀態是很復雜的。因為結石的分布是沒有規律的，而且有後遺癥。
所以我們必須回去搜索。尋找石頭會像移動的規則壹樣不規則。我們搜索壹座橋的長度，然後加上壹個巧妙的剪枝，在很短的時間內求解。可以稱之為O(m2)。【註:所謂這個詞已經成為湖南OI本世紀的流行詞】
【話題實現】
先搜索時間。時間復雜度為O(L)。從橋的壹邊到另壹邊，中間最多只有100塊石頭。假設橋長最大(109)，石頭數也最大(100)。這樣的話，中間肯定有很多“空條”(兩塊石頭裏的空白)。如果在處理時跳過這些，就只有m個操作。關鍵是找出每壹個可以跳過的“空條”。
我們可以先找出青蛙能跳出的所有可能性，再找出可以忽略的“空條”。
[特殊算法]
A[i]:第壹個I坐標的最小石子數，初始數是I坐標的石子數。
B[i]:第I塊石頭的坐標。
移動量規
a[0]= 0；
右n & gt=t
a[n]=min{a[n]+a[n-s]，a[n]+a[n-s-1]，...，a[n]+a[n-t]}
右側s =
a[n]=max{a[n]+a[n-s]，a[n]+a[n-s-1]，...，a[n]+a[0]}
但是，由於n較大，直接作用量規會超時。所以n要壓縮。
看坐標可以發現，如果b[I]-b[I-1]>；t，顯然對於b [I-1]+t
註意，在計算過程中，因為有些坐標永遠無法到達，所以需要使用布爾數組c[n]進行判斷。方法是，對於c[n]，如果0；s，c [n-t]，c [n-t+1]，...，c [n-s]都為假，那麽c[n]也為假。
程序:
var f:array [0..9]的longword
ts，stone:array [0..longint的100]；
j，I，s，t，l:longint；
k，os:字節；
tmp:long word；
函數gbs(l，r:byte):long word；
var i:字節；
開始
GBS:= 1；
for I:= l to r do GBS:= GBS * I；
結束；
開始
賦值(輸入，' river . in ')；
賦值(output，' river . out ')；
復位(輸入)；
重寫(輸出)；
filldword(f，sizeof(f) div 4，maxlongint)；
readln(l)；
readln(s，t，stone[0])；
for I:= 1 to stone[0]do read(stone[I])；
對於i:=1 to stone[0] do
對於j:=1至i-1 do
如果stone[j]& gt；stone[i]然後開始tmp:= stone[I]；stone[I]:= stone[j]；stone[j]:= tmp；結束；
ts[0]:= stone[0]；
ts[1]:= stone[1]mod(GBS(s，t))；
如果ts[1]=0那麽ts[1]:= t；
對於i:=2到stone[0] do
開始
ts[I]:= ts[I-1]+(stone[I]-stone[I-1])mod(GBS(s，t))；
if (ts[i]=ts[i-1])則ts[I]:= ts[I]+t；
if(stone[I]-stone[I-1]& lt；& gt1)且(ts[i]=ts[i-1]+1)則ts[I]:= ts[I]+t；
結束；
l:= ts[ts[0]]+(l-s-stone[stone[0]])mod s+t；
石頭:= ts
f[0]:= 0；
因為我願意
開始
OS:= 0；
for k:= 1 to stone[0]do if stone[k]= I然後開始OS:= 1；中斷結束；
tmp:= maxlongint；
for j:=i-t to i-s do
開始
如果j & lt0然後繼續；
如果j & gt然後我打破了；
如果tmp & gtf[j mod 10]+os然後tmp:= f[j mod 10]+OS；
結束；
f[I mod 10]:= tmp；
結束；
j:= maxlongint；
for I:= l-t to l do if j & gt；f[i mod 10]那麽j:= f[I mod 10]；
writeln(j)；
關閉(輸出)；
結束。