爱华网NOIP2005 提高组第二题
【问题描述】
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：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。
这题的状态方程是十分明显的，f[i]:=min(f[i-j]+b[i]),s=<j<=t;
这题的难点在于 状态压缩
l的范围太大了，而石子最多只有100个，说明在很长的一段距离中，青蛙不会遇到任何石子，却在做重复运动，于是我们进行状态压缩。
取 Ｓ，Ｔ的极限数据 ９ １０
思考过程如下（青蛙可能跳到的点）
第一步：９ １０
第二步：１８，１９，２０
第三步：２７，２８，２９，３０
第四步：３６，３７，３８，３９，４０
第五步：４５，４６，４７，４８，４９，５０
第六步：５４，５５，５６，５７，５８，５９，６０
第七步：６３～７０
第八步：７２～８０
第九步：８１～９０
到第九布为止，我们发现没两步之间能跳的点已经连成一段，也就是说从７２以后的所有点都可以通过组合的方式跳到，而这些点的ＤＰ值和它前面的点一样（跳到这个点的点）；所以当两个石子之间的距离大于７２时，我们可以将它压缩为７２，ＤＰ值不变（注意的是，压缩路劲的时候要整体操作，压缩前面点的时候，后面的点要依次前移）；
而当Ｓ＝Ｔ时，上面的推论不成立，所以要特殊处理..
（这题有个陷阱，它给出的数据是无序的，所以要先进行排序）；
这是我的标程：
rogram p1002;
var l,kk,s,t,m,i,j,temp,max:longint;
a:array[0..1000]of longint;
b,f:array[0..1000000]of longint;
begin
readln(l);
read(s,t,m);
for i:=1 to m do
read(a[i]);
kk:=0;
if s=t then｛处理Ｓ＝Ｔ｝时
beg in
for i:=1 to m do
if a[i] mod s =0 then inc(kk);
write(kk);
halt;
end;
for i:=1 to m-1 do｛数据排序｝
for j:=i+1 to m do
if a[i]>a[j] then begintemp:=a[i];a[i]:=a[j];a[j]:=temp;end;
for i:=1 to m do ｛路径压缩｝
if a[i]-a[i-1]>100 then
begin
kk:=a[i]-a[i-1]-100;
for j:=i to m do
a[j]:=a[j]-kk;
end;
fillchar(b,sizeof(b),0);
for i:=1 to m do
b[a[i]]:=1;
l:=a[m];{l赋值为最后一个石子距离}
for i:=1 to l+t do f[i]:=100;
f[0]:=0;
for i:= s to l+t do ｛注意ＤＰ的时候是l+T因为最有一步可以越过L}
for j:= s to t do
if (i-j>=0)and(f[i-j]+b[i]<f[i]) then f[i]:=f[i-j]+b[i];
max:=100;
for i:= l to l+t do
if f[i]<max then max:=f[i];
write(max);
end.
