LeetCode-python 403.青蛙过河

题目链接

难度：困难       类型： 数组、动态规划

一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。

给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

请注意：

石子的数量 ≥ 2 且 <1100；

每一个石子的位置序号都是一个非负整数，且其 <231；

第一个石子的位置永远是0。

示例1

示例2

dp[stones[i]]表示在第i个石头上可以向前跳的步长的集合

跳到第i个石头时，用当前能跳的步长往前跳，若能跳到石头上，则该石头的步长集合中添加该步长，若最后一块石头的步长集合不为空，则返回True，反之为False

本文链接： https://www.jianshu.com/p/037cc624e3c1

var

L,s,t,m,n,i,j,v,best:longint

x:array [0..100] of longint{由左而右记录每个石子的位置}

a:array [0..100,0..9] of longint{a[i,j]为青蛙跳到x[i]-j位置经过的最少石子数}

b:array [-10..90] of boolean{b[i]记录能否用s到t这t-s+1种距离从原点到达横坐标为i的位置}

function can(v:longint):boolean{判别青蛙能否跳到v}

begin

if v<0 then can:=false

else if v>=s*s-s{可以证明,当v≥s(s-1)时,一定可以用s和s+1两种跳跃距离到达位置v,所以要对s=t作特殊处理}

then can:=true else can:=b[v] end

{can} begin assign(input,'river.in')

reset(input){输入文件读准备}

readln(L)readln(s,t,m)

{读独木桥长度、青蛙一次跳跃的最小距离，最大距离和桥上的石子数}

for i:=1 to m do read(x[i]){输入每个石子在数轴上的位置}

readln

close(input){关闭输入文件}

for i:=1 to m-1 do{按照由左而右的顺序排列石子}

for j:=1 to m-1 do if x[j]>x[j+1] then begin v:=x[j]x[j]:=x[j+1]x[j+1]:=v end{ then } n:=mwhile x[n]>L do dec(n){去除独木桥外的石子}

if s=t{若青蛙每次跳跃的距离唯一，则青蛙过河最少需要踩到的石子数best即为坐标位置为s整倍数的石子数}

then begin best:=0

for i:=1 to n do

if x[i] mod s=0 then

inc(best)

assign(output,'river.out')

rewrite(output){输出文件写准备}

writeln(best){输出best后关闭输出文件并成功退出}

close(output)

halt

end{ then }

fillchar(b,sizeof(b),false)

b[0]:=true{计算小范围的情况}

for i:=1 to 90 do{递推每一个坐标位置}

for j:=s to t do {枚举青蛙一次跳跃的可能距离，计算青蛙能否跳到坐标位置i}

b[i]:=b[i] or b[i-j]

for i:=0 to n do{状态转移方程初始化}

for j:=0 to t-1 do

a[i,j]:=n+1x[0]:=0{在0位置处增加一个虚拟的石子}

a[0,0]:=0{ 青蛙在0位置起跳}

for i:=1 to n do{递推桥上的每一个石子}

for j:=0 to t-1 do{枚举每一个可能的跳前位置}

if x[i]-j<=x[i-1]{如果x[i]-j位置位于石子i-1的左端}

then a[i,j]:=a[i-1,j-x[i]+x[i-1]]

else begin{若x[i]-j位置位于石子i-1的右端,则枚举每一个可能的跳前}

for v:=0 to t-1 do if can(x[i]-j-x[i-1]+v) and (a[i-1,v]<a[i,j]) {若青蛙可以从x[i-1]-v跳到x[i]-j位置，且跳到x[i-1]-v位置经过的最少石子数为目前最少，则取跳到x[i-1]-v位置经过的最少石子数}

then

a[i,j]:=a[i-1,v]

if j=0 then inc(a[i,j]){若踩到第I个石子，则经过的石子数+1} end

{ else } best:=n+1

for i:=0 to t-1 do{枚举青蛙跳出独木桥前的最后一个起跳位置，计算经过的石子数，从中找出最优解}

if a[n,i]<best then

best:=a[n,i]

assign(output,'river.out')

rewrite(output){输出文件写准备}

writeln(best){输出最优解}

close(output){关闭输出文件}

end.

打字很累，我测试过的，对的，就cai我吧

O(∩_∩)O~~

---