高校问答小苍20分45秒是什么梗:NOIP2005提高组复赛第二题详细解答
来源：百度文库 编辑：高校问答 时间：2024/05/06 06:38:26
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
【输入文件】
输入文件river.in的第一行有一个正整数L（1 <= L <= 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
【输出文件】
输出文件river.out只包括一个整数，表示青蛙过河最少需要踩到的石子数。
【样例输入】
10
2 3 5
2 3 5 6 7
【样例输出】
2
【数据规模】
对于30%的数据，L <= 10000；
对于全部的数据，L <= 109。
我是刚学信息学的OIER
但我很想知道NOIP2005提高组复赛第二题详细解答
我目前只知道这题可以用动态规划解（有一点动态规划的基础，能解简单的
动态规划题）但不知道具体的编写思路和细节。
我还听说如果两个石子之间的距离如果大于90就可以当作90来做，不知道为
什么。请给出详细的说明。
注：不要说的太深奥，我看不懂的。我是学C看的懂一点PASCAL。C的程序代
码最好，PASCAL也行。程序代码必须有详细的注解。
初步分析：
设f(i)表示到达坐标i时最少踩到的石子数。
r(i)表示坐标i上有无石子，若有，r(i)=1，否则r(i)=0
f(i)=min{f(j)}+r(i)，其中s<=i-j<=t
边界f(0)=0
Ans=min{f(i)}，其中i>=L
该算法时间复杂度是O(L*(t-s))
深入分析：
直观上说，对于一大片没有石子的区域，我们进行动态规划是没有必要的。
可以证明，当空白区域大于某个max的时候，青蛙一定可以从该区域的一端跳到另一端。
事实上，对于跳跃区间[s,t]来说，max<100
所以我们可以将每段长度>max的空白区域压缩成max的长度。这样总的L’就只有m*max<=10000。
这样再进行前面的动态规划，复杂度是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>=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。
程序:
var f:array [0..9] of longword;
ts,stone:array [0..100] of longint;
j,i,s,t,l:longint;
k,os:byte;
tmp:longword;
function gbs(l,r:byte):longword;
var i:byte;
begin
gbs:=1;
for i:=l to r do gbs:=gbs*i;
end;
begin
assign(input,’River.in’);
assign(output,’River.out’);
reset(input);
rewrite(output);
filldword(f,sizeof(f) div 4, maxlongint );
readln(l);
readln(s,t,stone[0]);
for i:=1 to stone[0] do read(stone[i]);
for i:=1 to stone[0] do
for j:=1 to i-1 do
if stone[j]>stone[i] then begin tmp:=stone[i];stone[i]:=stone[j];stone[j]:=tmp; end;
ts[0]:=stone[0];
ts[1]:=stone[1] mod (gbs(s,t));
if ts[1]=0 then ts[1]:=t;
for i:=2 to stone[0] do
begin
ts[i]:=ts[i-1]+(stone[i]-stone[i-1]) mod (gbs(s,t));
if (ts[i]=ts[i-1]) then ts[i]:=ts[i]+t;
if (stone[i]-stone[i-1]<>1) and (ts[i]=ts[i-1]+1) then ts[i]:=ts[i]+t;
end;
l:=ts[ts[0]]+(l-s-stone[stone[0]]) mod s+t;
stone:=ts;
f[0]:=0;
for i:=s to l do
begin
os:=0;
for k:=1 to stone[0] do if stone[k]=i then begin os:=1;break end;
tmp:=maxlongint;
for j:=i-t to i-s do
begin
if j<0 then continue;
if j>l then break;
if tmp>f[j mod 10]+os then tmp:=f[j mod 10]+os;
end;
f[i mod 10]:=tmp;
end;
j:=maxlongint;
for i:=l-t to l do if j>f[i mod 10] then j:=f[i mod 10];
writeln(j);
close(output);
end.
有很多式子在这里没法打,你给我发邮件,我把word给你发过去
sbin_001@163.com