51Nod 1084-矩阵取数问题 V2

原题

时间限制：2 s  空间限制：131072 KB

Description

 

一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

 

例如：3 * 3的方格。

 

1 3 3

2 1 3

2 2 1

 

能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只计算1次。

 

Input

第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200) 第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Sample Input

3 3

1 3 3

2 1 3

2 2 1

Sample Output

17

 

题意

在一个n*m的矩阵中找出两条从(1,1)走到(n,m)的路，使得两条路上经过点上的数相加和最大。

题解

这道题首先想到的是贪心，先找出一条路的和的最大值，并将走过的点全部赋值为0，再dp一次求剩余的点，但仔细想想便发现这是错的，因为得出的解并非一定为最大值。

接着就只能dp了，目前已掌握两种方法：

方法1：

既然要求的是两条路的最大值，那就让两条路一起dp，用f[i,j,k,l]表示两条同时从(1,1)分别走到(i,j)和(k,l)的路的最大和，最后要求的就是f[n,m,n,m]，此方法效率O(n^2*m^2)。

代码如下：

uses math;
var f:array[0..50,0..50,0..50,0..50] of longint;
var n,x,y,c,i,j,k,l,m:longint;
var t:array[1..50,1..50] of longint;
begin
  readln(n,m);
  for i:=1 to n do for j:=1 to m do read(t[i,j]);
  for i:=1 to n do
  for j:=1 to m do//枚举顶点x
  for k:=1 to n do
  for l:=1 to m do//枚举顶点y
  begin
    f[i,j,k,l]:=max(max(max(f[i-1,j,k-1,l],f[i-1,j,k,l-1]),f[i,j-1,k,l-1]),f[i,j-1,k-1,l])+t[i,j]+t[k,l];//求4种情况的最大值(x点从上方走来，y点从左方；x点从上方走来，y点也从上方；x点从左方走来，y点从上方；x点从左方走来，y点也从左方)
    if (i=k)and(j=l) then dec(f[i,j,k,l],t[i,j]);//两点重叠则减其一
  end;
  writeln(f[n,m,n,m]);//同时走到(n,m)时的答案
end.

 

方法2：

楼上那代码四重循环太暴力了，只能过CodeVS的水数据，51Nod的大数据根本过不了【n,m<=200

那我们必须寻求效率更高的方法，只用三重循环。

事实上我们可以发现，f[i,j,k,l]不管是多少，总是存在i+j=k+l，这是因为他们走过的步数是相同的，那我们何不用这个步数来代替(i和k)或(j和l)呢？

如图为一个5*5的矩阵，上面所标记的数字为从(1,1)走到该点的步数step。

那现在我们只需要3重循环了，假设我们用step替换掉(j和l)，那么j和l也能用step,i和k算出，从而重新得到两个点的坐标。

下面代码：

uses math;
var f:array[0..400,0..200,0..200] of longint;
var a:array[1..200,1..200] of longint;
var n,m,i,j,k:longint;
begin
  readln(n,m);
  for i:=1 to n do for j:=1 to m do read(a[i,j]);
  for i:=1 to n+m-1 do//枚举步数step
  for j:=1 to n do//枚举x点的纵坐标
  for k:=1 to n do//枚举y点的纵坐标
  begin
    if (i-j+1<1)or(i-k+1<1) then break;//纵坐标超过步数范围则退出
    f[i,j,k]:=max(f[i-1,j,k],max(f[i-1,j-1,k-1],max(f[i-1,j,k-1],f[i-1,j-1,k])))+a[j,i-j+1]+a[k,i-k+1];//原理与上一种方法相同，并由步数可以推出点x与点y的坐标
    if j=k then dec(f[i,j,k],a[j,i-j+1]);//坐标相同减其一
  end;
  writeln(f[n+m-1,n,n]);//最终答案
end.

欢迎转载，若转载请注明出处，单手打字不易。