回 帖 发 新 帖 刷新版面

主题:[讨论]宝藏问题

给定一个二维数组,从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.
谢谢!
不胜感激!

回复列表 (共3个回复)

沙发

不如写成递归
以楼住的意思maxn=20
那么递归最多不过20层 写成递归的话可读性大大提高 也不容易出错
但我还是建议用动态规划的方法
有好方法为什么不用呢
给段动规代码吧

init a[1..n,1..n];
fillchar(d,sizeof(d),0); d[1,1]:=a[1,1];
for i:=1 to n do
 for j:=1 to n do
  d[i,j]:=max{d[i-1,j],d[i,j-1]}+a[i,j];
print;

板凳

至于程序的毛病 我觉的是 c d 没有判断出界
即 if b[k]=1 不是可以向右走的充要条件

3 楼

谢谢!

我来回复

您尚未登录,请登录后再回复。点此登录或注册