比赛 20121106 评测结果 WEEEEEEE
题目名称 过河 最终得分 0
用户昵称 CAX_CPG 运行时间 0.843 s
代码语言 Pascal 内存使用 38.54 MiB
提交时间 2012-11-06 11:33:33
显示代码纯文本
uses math;

var f:array[-1..1000,-1..10000]of longint;
    a,b:array[0..1001]of longint;
    i,n:longint;

function g(x,y,z:longint):longint;
var i:longint;
begin
 if f[x,y]<>f[-1,-1] then exit(f[x,y]);
 if x=n+1 then begin f[x,y]:=0;exit(0);end;
 if x>=n-4 then begin f[x,y]:=1;exit(1);end;
 for i:=1 to 5 do
  begin
   if (x+i<=n+1) then if (y mod(a[x+i]+b[x+i])+1<=a[x+i])or(x+i=n+1)
    then if x+i<>z then f[x,y]:=min(f[x,y],g(x+i,y+1,x)+1);
   if (x-i>=0)then if (y mod(a[x-i]+b[x-i])+1<=a[x-i])or(x-i=0)
    then if x-i<>z then f[x,y]:=min(f[x,y],g(x-i,y+1,x)+1);
  end;
 if x<>z then f[x,y]:=min(f[x,y],g(x,y+1,x)+1);
 exit(f[x,y]);
end;

begin
 assign(input,'rivera.in');reset(input);
 assign(output,'rivera.out');rewrite(output);
 readln(n);
 for i:=1 to n do readln(a[i],b[i]);
 a[n+1]:=1;b[n+1]:=1;a[0]:=1;b[0]:=1;
 fillchar(f,sizeof(f),$7f);
 if g(0,0,-1)<>f[-1,-1]then writeln(g(0,0,-1))else writeln('NO');
end.