- 三取方格数
- 2009-08-14 18:33:03 @
不知道为什么错了,我连程序的每一步都运行过,甚至试过打印每一步的动规f和路径,完全没发现问题,到底是怎么了?
我的程序:
var i,j,k,l,o,p,n,t:integer;
tu:array[0..20,0..20]of integer;
f:array[0..20,0..20]of integer;
w:array[0..20,0..20,1..2]of integer;
function max(a,b:integer):integer;
begin
max:=a;
if(b>a)then max:=b;
end;
begin
readln(n);
for i:=1 to n do begin
for j:=1 to n do read(tu);
end;
p:=0;
for o:=1 to 3 do begin
for i:=1 to n do begin
f[i][i]:=max(f[i],f[i])+tu[i][i];
if(f[i]>f[i])then begin w[i][i][1]:=i-1; w[i][i][2]:=i; end
else begin w[i][i][1]:=i; w[i][i][2]:=i-1; end;
for j:=i+1 to n do begin
f[j][i]:=max(f[j-1][i],f[j])+tu[j][i];
f[i][j]:=max(f[j],f[i][j-1])+tu[i][j];
if(f[j-1][i]>f[j])then begin w[j][i][1]:=j-1; w[j][i][2]:=i; end
else begin w[j][i][1]:=j; w[j][i][2]:=i-1; end;
if(f[j]>f[i][j-1])then begin w[i][j][1]:=i-1; w[i][j][2]:=j; end
else begin w[i][j][1]:=i; w[i][j][2]:=j-1; end;
end;
end;
i:=n;
j:=n;
while (i0)or(j0) do begin
tu[i][j]:=0;
t:=i;
i:=w[i][j][1];
j:=w[t][j][2];
end;
p:=p+f[n][n];
end;
writeln(p);
end.
相当令人郁闷啊……