2295 - L1004 的题解

回去原题
#用DP做,但注意最后一个[n,n]的位置有权值,不为0

var
  v:array[1..50,1..50] of longint;
  f:array[0..51,0..51,0..51,0..51] of longint;
  m,n,i,j,k,q:longint;
function  max(a,b:longint):longint;
begin
  if a>b then  exit(a)
  else  exit(b);
end;
begin
  readln(n);
  fillchar(f,sizeof(f),0);
  readln(m,k,q);
  fillchar(v,sizeof(v),0);
  while (m<>0)or(k<>0) do
  begin
    v[m,k]:=q;
    readln(m,k,q);
  end;
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        for q:=1 to n do
          if (i<>k)or(j<>q) then
            f[i,j,k,q]:=v[i,j]+v[k,q]+max(max(f[i-1,j,k,q-1],f[i,j-1,k,q-1]),max(f[i-1,j,k-1,q],f[i,j-1,k-1,q]))
          else
            f[i,j,k,q]:=v[i,j]+max(max(f[i-1,j,k,q-1],f[i,j-1,k,q-1]),max(f[i-1,j,k-1,q],f[i,j-1,k-1,q]));
  writeln(max(f[n-1,n,n,n-1],f[n,n-1,n-1,n])+v[n,n]);
end.