Question

pascal noip2008 传纸条

程序哪错了？？？？
var v:array[1..50,1..50]of shortint;
a:array[0..50,0..50,0..50]of integer;
i,j,k,m,n,i1,j1:shortint;

function sub(x1,y1,x2:shortint):integer;
var s,e:integer;
y2:shortint;
begin
if a[x1,y1,x2]<>-1 then begin sub:=a[x1,y1,x2];end
else
begin
y2:=x1+y1-x2;
if (x1-1<>x2)and(x1-1>0)and(y2-1>0) then begin e:=sub(x1-1,y1,x2)+v[x1-1,y1]+v[x2,y2-1];end;

if (x1-1<>x2-1)and(x1-1>0)and(x2-1>0) then begin s:=sub(x1-1,y1,x2-1)+v[x1-1,y1]+v[x2-1,y2];end;
if e<s then e:=s;

if (x1<>x2)and(y1-1>0)and(y2-1>0) then begin s:=sub(x1,y1-1,x2)+v[x1,y1-1]+v[x2,y2-1];end;
if e<s then e:=s;

if (x1<>x2-1)and(y1-1>0)and(x2-1>0) then begin s:=sub(x1,y1-1,x2-1)+v[x1,y1-1]+v[x2-1,y2];end;
if e<s then e:=s;

sub:=e;
a[x1,y1,x2]:=e;

end;
end;

begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do
begin
read(v[i,j]);
for k:=1 to m do a[i,j,k]:=-1;
end;

a[1,2,2]:=0;a[2,1,1]:=0;

writeln(sub(m,n,m));

end.
12行和13行之间少打了s=0;e:=0;
我的问题是为什么超时???
3维DP应该快才对呀,我不要代码,我要求解释...

Answer 1

那个楼主，你的程序应该没有问题啊，非常完美啊。我在清澄测试器上测试了一下，你的程序很好，几乎都是0.02s过的。如果你用的是清澄测试的话，可能（只是可能）是由于没有关闭文件导致超时。如果你是用oj的话，应该是该网站的问题。 你的成绩就是那个新建文件夹的。

Answer 2

复杂度过高？
给你我的代码
var
f:array[1..50,1..50,1..50,1..50]of longint;
a:array[1..50,1..50]of longint;
i,j,k,l,n,m:longint;
procedure init;
var
i,j:longint;
begin
readln(n,m);
for i:=1 to n do
begin
for j:=1 to m do
read(a[i,j]);
readln;
end;
end;
function max(a,b:longint):longint;
var
ans:longint;
begin
ans:=0;
if a>ans then ans:=a;
if b>ans then ans:=b;
exit(ans);
end;
begin
init;
fillchar(f,sizeof(f),0);
for i:=1 to n do
for j:=1 to m do
for k:=1 to n do
for l:=1 to m do
if ((i<>k)and(j<>l))or((j=m)and(k=n)and(l=m))then
begin
if (i<>1)and(k<>1) then
f[i,j,k,l]:=max(f[i,j,k,l],f[i-1,j,k-1,l]);
if (j<>1)and(l<>1)then
f[i,j,k,l]:=max(f[i,j,k,l],f[i,j-1,k,l-1]);
if (i<>1)and(l<>1) then
f[i,j,k,l]:=max(f[i,j,k,l],f[i-1,j,k,l-1]);
if (j<>1)and(k<>1)then
f[i,j,k,l]:=max(f[i,j,k,l],f[i,j-1,k-1,l]);
inc(f[i,j,k,l],a[i,j]+a[k,l]);
end;
writeln(f[n,m,n,m]) ;
end.

Answer 3

递归万年慢，尝试非递归。
建议这种题目最好不要用记忆化搜索。。。
总之递归就是会囧，会有各种问题。

以后你会发现递归天天爆栈（就是说递归大概10000次上下就会挂）。所以能不用递归尽量别用递归。

Answer 4

递归在数据比较大的情况下会超时，2维DP可以轻松解决

Answer 5

程序无错，鉴定完毕