这里是i==k && j==l就去重减去一次,但是为什么可以防止两条路径相交呢?
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 55;
int g[N][N];
int f[N][N][N][N];
int n, m;
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
int a, b, c;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
cin >> g[i][j];
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
for(int k = 1 ; k <= n ; k ++)
for(int l = 1 ; l <= m ; l ++)
{
f[i][j][k][l] = max( max(f[i-1][j][k-1][l], f[i-1][j][k][l-1]), max(f[i][j-1][k-1][l], f[i][j-1][k][l-1]) ) + g[i][j] + g[k][l];
if(i == k && j == l)
f[i][j][k][l] -= g[i][j];
}
cout << f[n][m][n][m];
}