题解 P1006 【传纸条】

b2109436454 · 2017-11-07 16:56:06 · 题解

不妨假设同时分两路走

则容易得到状态转移方程为

dp[x1,y1,x2,y2]:=max(dp[x1-1,y2,x2-1,y2],dp[[x1,y1-1,x2,y2-1],dp[x1-1,y1,x2,y2-1],dp[x1,y1-1,x2-1,y2])+a[x1,y1]+a[x2,y2];

容易发现并证明（略）

x1+y1=x2+y2

则可以压缩为三维

dp[k,x1,x2]:=max(dp[k-1,x1,x2],dp[k-1,x1-1,x2],dp[k-1,x1,x2-1],dp[k-1,x1-1,x2-1])+a[x1,k-x1]+a[x2,k-x2];

容易发现很多内容是冗余的，采用滚动数组优化，只要用二维

dp2[x1][x2]:=max(dp[x1-1][x2-1],dp[x1-1][x2],dp[x1][x2-1],dp[x1][x2])+a[x1][k-x1]+a[x2][k-x2];

并且每次更新dp数组 即可起到滚动的作用

var 
dp,dp2:array[0..50,0..50]of integer;
a:array[0..50,0..50]of integer;
m,n,i,j,x1,x2,k:integer;
function min(a,b:integer):integer;
begin
if a<b then exit(a)
else exit(b);
end;
function max(a,b,c,d:integer):integer;
begin
if (a>=b)and(a>=c)and(a>=d) then exit(a);
if (b>=c)and(b>d) then exit(b);
if c>d then exit(c);
exit(d);
end;
begin
  read(m,n);
  for i:=1 to m do
    for j:=1 to n do
      read(a[i,j]);
  for k:=1 to m+n do
  begin
    for x1:=1 to min(m,k) do
      for x2:=1 to min(m,k) do
        if (x1<>x2)or(k=1)or(k=m+n) then
          dp2[x1][x2]:=max(dp[x1-1][x2-1],dp[x1-1][x2],dp[x1][x2-1],dp[x1][x2])+a[x1][k-x1]+a[x2][k-x2];//优化，压缩数组
    dp:=dp2;//更新
  end;
  writeln(dp[m,m]);
end.