主题:[讨论]宝藏问题
给定一个二维数组,从1,1的格子向下找,直到最后一行的最后一列,要求取值必须最大,且只能向右或向下
输入:N
然后是N行N列的二维数组
输出:最大值
例子:
3
1 3 2
15 4 8
20 14 7
输出:57
我知道用回溯法(也可以用动态规划)去做也编写了程序源代码,可是不知道为什么,用FP运行时,总是有错误,请各位帮助解决:
var
a:packed array[1..20,1..20] of longint;
b:packed array[1..1000] of integer;
c:packed array[1..1000] of integer;
d:packed array[1..1000] of integer;
n,i,j,k,l,s,max:longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
readln;s:=a[1,1];
k:=2;c[1]:=1;d[1]:=1;
while b[1]=0 do
begin
b[k]:=b[k]+1;
if b[k]<=2 then
begin
if b[k]=1 then
begin
k:=k+1;
c[k]:=c[k-1]+1;
d[k]:=d[k-1]+0;
s:=s+a[c[k],d[k]];
end
else
begin
k:=k+1;
c[k]:=c[k-1]+0;
d[k]:=d[k-1]+1;
s:=s+a[c[k],d[k]];
end;
end
else
begin
k:=k-1;
b[k+1]:=0;
s:=s-a[c[k+1],d[k+1]];
end;
if k=2*n-1 then
if s>max then max:=s;
end;
end.
谢谢!
不胜感激!
输入:N
然后是N行N列的二维数组
输出:最大值
例子:
3
1 3 2
15 4 8
20 14 7
输出:57
我知道用回溯法(也可以用动态规划)去做也编写了程序源代码,可是不知道为什么,用FP运行时,总是有错误,请各位帮助解决:
var
a:packed array[1..20,1..20] of longint;
b:packed array[1..1000] of integer;
c:packed array[1..1000] of integer;
d:packed array[1..1000] of integer;
n,i,j,k,l,s,max:longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
readln;s:=a[1,1];
k:=2;c[1]:=1;d[1]:=1;
while b[1]=0 do
begin
b[k]:=b[k]+1;
if b[k]<=2 then
begin
if b[k]=1 then
begin
k:=k+1;
c[k]:=c[k-1]+1;
d[k]:=d[k-1]+0;
s:=s+a[c[k],d[k]];
end
else
begin
k:=k+1;
c[k]:=c[k-1]+0;
d[k]:=d[k-1]+1;
s:=s+a[c[k],d[k]];
end;
end
else
begin
k:=k-1;
b[k+1]:=0;
s:=s-a[c[k+1],d[k+1]];
end;
if k=2*n-1 then
if s>max then max:=s;
end;
end.
谢谢!
不胜感激!