pascal难题，求教高手！

超级蛙···
我记得这题有个重要优化，当n>=15还是多少时就没有跳不到的荷叶

DP=动态规划
如果那个优化我没记错的话这题其余部分暴力就可以了

Program zd1;

Var

Flag : Array[0..10000] Of Boolean;

f : Array[0..10000] Of Longint;

a : Array[0..101] of Longint;

s, t, m, l, i, j, tail, min: Longint;

Procedure Qsort1(l, r : Longint);{快排}

Var

i, j, x, t : Longint;

Begin

i := l;j := r;x := A[(i+j) Shr 1];

Repeat

While (x>a[i]) Do Inc(i);

While (x
if i<=j Then Begin

t := A[i];

A[i] := A[j];

A[j] := t;

Inc(i);

DEc(j);

End;

Until i>j;

if l
if I
End;

Begin

Readln(l);

Readln(s, t, m);

For i :=1 to m Do Read(a[i]);

Qsort1(1, m);

if s=t then begin {单独处理}

Min := 0;

For i :=1 to m Do begin

If a[i] mod s=0 Then Inc(Min);

End;

Writeln(min);

Halt;

End;

tail := 0;a[0] := 0;

Inc(m);

A[m] := l;

For i :=1 to m Do begin

if A[i] - A[i - 1]>20 Then Begin {状态压缩}

Flag[tail + 20] := True;

tail := tail + 20;

End

Else Begin

Flag[tail + A[i] - a[i-1]] := True;

tail := tail + A[i]-a[i-1];

End;

End;

F[0] := 0;

For i := 1 to s-1 Do

F[i] := 10000;

For i :=s To t-1 Do begin {赋初始值}

If Flag[i] Then F[i] := 1 Else F[i] := 0;

End;

For i := t to tail Do begin {动态规划}

Min := Maxlongint;

For j := s to t Do begin

If F[i-j]
End;

If Flag[i] Then F[i] := Min+1 Else F[i] := Min;

End;

Writeln(F[tail]-1); {输出最好值}

End.

DP+状态压缩
超过200就可以得到任意点可达到
然后就可以了

Program zd1;

Var

Flag : Array[0..10000] Of Boolean;

f : Array[0..10000] Of Longint;

a : Array[0..101] of Longint;

s, t, m, l, i, j, tail, min: Longint;

Procedure Qsort1(l, r : Longint);{快排}

Var

i, j, x, t : Longint;

Begin

i := l;j := r;x := A[(i+j) Shr 1];

Repeat

While (x>a[i]) Do Inc(i);

While (x
if i<=j Then Begin

t := A[i];

A[i] := A[j];

A[j] := t;

Inc(i);

DEc(j);

End;

Until i>j;

if l
if I
End;

Begin

Readln(l);

Readln(s, t, m);

For i :=1 to m Do Read(a[i]);

Qsort1(1, m);

if s=t then begin {单独处理}

Min := 0;

For i :=1 to m Do begin

If a[i] mod s=0 Then Inc(Min);

End;

Writeln(min);

Halt;

End;

tail := 0;a[0] := 0;

Inc(m);

A[m] := l;

For i :=1 to m Do begin

if A[i] - A[i - 1]>20 Then Begin {状态压缩}

Flag[tail + 20] := True;

tail := tail + 20;

End

Else Begin

Flag[tail + A[i] - a[i-1]] := True;

tail := tail + A[i]-a[i-1];

End;

End;

F[0] := 0;

For i := 1 to s-1 Do

F[i] := 10000;

For i :=s To t-1 Do begin {赋初始值}

If Flag[i] Then F[i] := 1 Else F[i] := 0;

End;

For i := t to tail Do begin {动态规划}

Min := Maxlongint;

For j := s to t Do begin

If F[i-j]
End;

If Flag[i] Then F[i] := Min+1 Else F[i] := Min;

End;

Writeln(F[tail]-1); {输出最好值}

End.
DP=动态规划
如果那个优化我没记错的话这题其余部分暴力就可以了

回答