讨论 - 请大牛来帮忙看一下关于过河卒的题目

linyanghui2009 2010-05-25 05:28:00

点我顶贴收藏删除

{n+}

program asdf;

const s:array[1..2,0..8]of longint=((0,1,1,2,2,-1,-1,-2,-2),(0,2,-2,1,-1,2,-2,1,-1));

var i,j,q,w,e,r:longint;

a:array[-1..21,-1..21]of comp;

begin

read(q,w,e,r);

fillchar(a,sizeof(a),0);

for i:=0 to 8 do

a[e+s[1,i],r+s[2,i]]:=-1;

a[0,0]:=-2;

for i:=0 to q do

for j:=0 to w do

begin

if a[i,j]<0

then if a[i,j]=-2 then a[i,j]:=1 else a[i,j]:=0

else a[i,j]:=a[i-1,j]+a[i,j-1];

end;

writeln(a[q,w]:0:0);

end.

#1 袁金松@2010-04-04 21:50:00

回复删除

我是这样做的：

var

a:array[-1000..101000] of longint;

f,r:array[-1000..1000000] of longint;

i,j,k,m,n,s,t,l,min,temp:longint;

procedure quick(h,t:longint);

var

i,j,k,s:longint;

begin

i:=h;

j:=t;

k:=a[(i+j) div 2];

repeat

while a[i]<k do inc(i);

while a[j]>k do dec(j);

if i<=j then begin

s:=a[i]; a[i]:=a[j]; a[j]:=s;

inc(i); dec(j);

end;

until i>j;

if i<t then quick(i,t);

if h<j then quick(h,j);

end;

begin

readln(l);

readln(s,t,m);

fillchar(f,sizeof(f),0);

a[0]:=0;

a[m+1]:=l;

for i:=1 to m do

read(a[i]);

quick(1,m);

if s=t then begin

min:=0;

for i:=1 to m do

if a[i] mod s=0 then

inc(min);

writeln(min);

halt;

end;

for i:=0 to m do begin

if a[i+1]-a[i]>temp+100 then

inc(temp,a[i+1]-a[i]-temp-100);

dec(a[i+1],temp);

end;

for I:=1 to m do

r[a[i]]:=1;

l:=a[m+1];

for i:=1 to l do

begin

min:=maxint;

for j:=s to t do

begin

if i>=j then

if r[i]+f[i-j]<min then

min:=r[i]+f[i-j];

f[i]:=min;

end;

writeln(f[l]);

end.

begin

readln(s,t,w);

n:=t-s+1;

up:=0;

for u:=1 to w do

begin

read(ch);

a[u]:=ord(ch)-96-s+1;

end;

slak(a[1],1,true);

end.

#2 樱@2010-04-04 21:56:00

回复删除

var

a:array[-1000..101000] of longint;

f,r:array[-1000..1000000] of longint;

i,j,k,m,n,s,t,l,min,temp:longint;

procedure quick(h,t:longint);

var

i,j,k,s:longint;

begin

i:=h;

j:=t;

k:=a[(i+j) div 2];

repeat

while a[i]<k do inc(i);

while a[j]>k do dec(j);

if i<=j then begin

s:=a[i]; a[i]:=a[j]; a[j]:=s;

inc(i); dec(j);

end;

until i>j;

if i<t then quick(i,t);

if h<j then quick(h,j);

end;

begin

readln(l);

readln(s,t,m);

fillchar(f,sizeof(f),0);

a[0]:=0;

a[m+1]:=l;

for i:=1 to m do

read(a[i]);

quick(1,m);

if s=t then begin

min:=0;

for i:=1 to m do

if a[i] mod s=0 then

inc(min);

writeln(min);

halt;

end;

for i:=0 to m do begin

if a[i+1]-a[i]>temp+100 then

inc(temp,a[i+1]-a[i]-temp-100);

dec(a[i+1],temp);

end;

for I:=1 to m do

r[a[i]]:=1;

l:=a[m+1];

for i:=1 to l do

begin

min:=maxint;

for j:=s to t do

begin

if i>=j then

if r[i]+f[i-j]<min then

min:=r[i]+f[i-j];

f[i]:=min;

end;

writeln(f[l]);

end.

begin

readln(s,t,w);

n:=t-s+1;

up:=0;

for u:=1 to w do

begin

read(ch);

a[u]:=ord(ch)-96-s+1;

end;

slak(a[1],1,true);

end.

#3 灌水专用号@2010-04-04 22:52:00

回复删除

顶

#4 904011766@2010-05-06 16:48:00

回复删除

过河卒AC答案！！！

var

n,m,x,y:int64;

i,j:longint;

a:array[-1..1372,-1..1824]of int64;

begin

read(n,m,x,y);

a[0,0]:=1;

for i:=0 to n do

for j:=0 to m do

begin

if (i=0)and(j=0)then continue;

a[i,j]:=a[i-1,j]+a[i,j-1];

if (i=x)and(y=j)then a[i,j]:=0;

if(abs(x-i)=2)and(abs(y-j)=1)then a[i,j]:=0;

if(abs(x-i)=1)and(abs(y-j)=2)then a[i,j]:=0;

end;

write(a[n,m]);

end.

#5 naocan@2010-05-25 05:28:00

回复删除

换个方式么？ AC的，你看看

var g,h,x1,y1,x2,y2,mn:integer;

a:array[-2..22,-2..22] of int64;

begin

read(x1,x2,y1,y2);

a[0,0]:=1;

a[y1,y2]:=-1;

a[y1+2,y2+1]:=-1;

a[y1-2,y2+1]:=-1;

a[y1+2,y2-1]:=-1;

a[y1-2,y2-1]:=-1;

a[y1+1,y2+2]:=-1;

a[y1-1,y2+2]:=-1;

a[y1+1,y2-2]:=-1;

a[y1-1,y2-2]:=-1;

h:=1;

for g:=1 to x2 do

if a[0,g]<>-1 then a[0,g]:=1 else break;

for g:=1 to x1 do

if a[g,0]<>-1 then a[g,0]:=h else h:=-1;

for g:=1 to x1 do

for h:=1 to x2 do

if a[g,h]<>-1 then

if (a[g-1,h]=-1) and (a[g,h-1]=-1) then a[g,h]:=-1 else

if a[g-1,h]<>-1 then begin

if a[g,h-1]<>-1 then begin

a[g,h]:=a[g,h-1]+a[g-1,h];

end else a[g,h]:=a[g-1,h]; end else a[g,h]:=a[g,h-1];

write(a[x1,x2]);

end.