算法思路
相比于AcWing 1027. 方格取数 :
-
两个方向对称传递
-
同一个格子第二次被取是不允许的(而不是等于
0
)
对于两个方向对称传递, 因为我们考虑的是路径的值, 这其中不用考虑方向性. 所以实际上与方格取数
同
方向取2
次等价. 对于同一格子只能被取以此, 可以判断若在非起点
/终点
处两条路径重合, 则跳过
此次运算; 或者可以直接用方格取数的代码
,一位朋友已经证明两者等价 .
代码实现
这里仅给出对同一格子采取跳过方案的代码实现.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n, m;
int w[N][N];
int dp[N + N][N][N];
int main()
{
cin >> n >> m;
for( int i = 1; i <= n; i ++ )
for( int j = 1; j <= m; j ++ )
cin >> w[i][j];
for( int k = 2; k <= n + m; k ++ )
for( int i1 = 1; i1 <= n; i1 ++ )
for( int i2 = 1; i2 <= n; i2 ++ )
{
int j1 = k - i1, j2 = k - i2;
if( 1 <= j1&&j1 <= m && 1 <= j2&&j2 <= m )
{
if( i1 == i2 )
{//两条路径在同一格子
if( !(i1 == 1 && j1 == 1) && !(i1 == n && j1 == m) )
continue; //不是起点也不是终点
}
int t = w[i1][j1] + w[i2][j2];
int &x = dp[k][i1][i2];
x = max( x, dp[k-1][i1-1][i2-1] );
x = max( x, dp[k-1][i1][i2-1] );
x = max( x, dp[k-1][i1-1][i2] );
x = max( x, dp[k-1][i1][i2] );
x += t;
}
}
cout << dp[n + m][n][n] << endl;
return 0;
}