這是解題報告
第二題 過河-River
[問題分析]
此題初看是壹個典型的搜索題。從河的壹側到河的另壹側，要找最少踩到的石頭數。但從數據範圍來看。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>=t
a[n]=min{a[n]+a[n-s],a[n]+a[n-s-1], ...,a[n]+a[n-t]}
對s=<n<t
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<n<b[i]，a[n]總是等於a[b[i-1]]..a[b[i-1]+t]中的數，因此可對其進行壓縮。
註意，在計算過程中，由於其中有壹些坐標是永遠走不到的，因此需要用壹個布爾型的數組c[n]進行判斷。方法是，對於c[n],如果0<n<s,則c[n]為false，如果n>s,c[n-t],c[n-t+1],...,c[n-s]都為false,則c[n]也為false。
這個我試了,是對的
type arr=array[0..100000] of longint;
var a,f,stone,stone2:arr;
l,s,x,t,m,n,o,p,i,j,k,min:cardinal;
procedure deal;
var i:longint;
begin
stone[0]:=0;
stone[m+1]:=l;
for i:=1 to m+1 do
if stone[i]-stone[i-1]>=100 then stone2[i]:=stone2[i-1]+100
else stone2[i]:=stone2[i-1]+stone[i]-stone[i-1];
end;
begin
readln(l);
readln(s,t,m);
for i:=1 to m do
read(stone[i]);
if s=t then begin
for i:=1 to m do
if stone[i] mod s=0 then inc(o);
writeln(o);
end
else begin
for i:=1 to m-1 do
for j:=1 to m-i do
if stone[j]>stone[j+1] then begin
stone[0]:=stone[j];
stone[j]:=stone[j+1];
stone[j+1]:=stone[0];
end;
Deal;
l:=stone2[m+1];
for i:=1 to m do
a[stone2[i]]:=1;
f[0]:=0;
for i:=1 to l+t do begin
f[i]:=maxlongint-1;
for j:=t downto s do
if i<j then break
else
if (f[i-j]+a[i])<f[i] then f[i]:=f[i-j]+a[i];
end;
min:=maxlongint;
for i:=l to l+t do begin
if f[i]<min then min:=f[i];
end;
writeln(min);
end;
end.
說了就是狀態壓縮dp