查人人中国名人网合作协议纠纷:请教高手们一道编程题
来源：百度文库 编辑：查人人中国名人网 时间：2024/05/06 12:58:55
给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你确定青蛙要想过河，最少需要踩到的石子数。
对于30%的数据，L <= 10000；
对于全部的数据，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
最好是C或C++语言的,希望高手门能讲解一下,小弟在这里先谢谢各位
OI的题吧
我觉得用动态规划做就可以了
从第一点开始， 记录到达每一个点所需的最少步数
类似于求最长递增或递减序列问题:)
Program p1002;
Var L,s,t,m:longint;
a:array[1..102] of longint;
f:array [0..10000] of 0..1;
Procedure init;
var i,j,x,y,z:longint;
begin
readln(L);
readln(s,t,m);
fillchar(f,sizeof(f),0);
if t>s then begin
for i:=1 to m do read(a[i]);
readln;
for i:=1 to m do
for j:=i+1 to m do
if a[i]>a[j] then begin x:=a[i]; a[i]:=a[j]; a[j]:=x; end;
y:=0; z:=0;
for i:=1 to m do begin
a[i]:=a[i]-z;
if a[i]-y>100 then begin
z:=z+a[i]-y-100;
a[i]:=y+100;
end;
y:=a[i];
f[y]:=1;
end;
L:=L-z;
if L-a[m]>100 then L:=a[m]+100;
end else
begin
z:=0;
for i:=1 to m do begin
read(x);
if (x mod s)=0 then z:=z+1;
end;
readln;
writeln(z);
close(input);
close(output);
halt;
end;
end;
Procedure find;
var i,j,u:longint;
w:array [0..10000] of byte;
begin
fillchar(w,sizeof(w),0);
for i:=L downto 0 do begin
u:=200;
for j:=s to t do
if (w[i+j]<u) then u:=w[i+j];
w[i]:=u+f[i];
end;
writeln(w[0]);
end;
Begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
init;
find;
close(input);
close(output);
End.
不会