f[k][i][j]
:当前两个点的x+y等于k,第一个点x为i,第二个点x为j
本题可以转化为从左上角往右下角同时传两个纸条,在传输过程中没有交点,所以可以dp为两个点的位置
所以有状态转移方程为:
if(i != j) //当前状态的两个点没有重合
for(int a = 0; a <= 1; a ++)//可能存在有i-a == j-b的情况,这种情况f一定为0,所以不会是max
for(int b = 0; b <= 1; b ++)
f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int w[N][N], f[2*N][N][N];//f[k][i][j]:当前两个点的x+y等于k,第一个点x为i,第二个点x为j
int n, m;
int main()
{
cin >> m >> n;
//memset(w, 128, sizeof w);
for(int i = 1; i <= m; i ++)
for(int j = 1; j <= n; j ++)
scanf("%d", &w[i][j]);
// 1 <= i <= m 1 <= k-i <= n ----> max(1, k-n) <= i <= min(m, k-1);
// 1 <= j <= m 1 <= k-j <= n ----> max(1, k-n) <= j <= min(m, k-1);
//两个人同时从(1, 1)出发
for(int k = 2; k <= n + m; k ++)
for(int i = max(1, k-n); i <= min(m, k-1); i ++)
for(int j = max(1, k-n); j <= min(m, k-1); j ++)
{
//当前状态可以从四种状态转移过来,同时那四种状态的i+j一定小于k,所以一定被遍历过
if(i != j) //当前状态的两个点没有重合
for(int a = 0; a <= 1; a ++)//可能存在有i-a == j-b的情况,这种情况f一定为0,所以一定不会是max
for(int b = 0; b <= 1; b ++)
f[k][i][j] = max(f[k][i][j], f[k-1][i-a][j-b] + w[i][k-i] + w[j][k-j]);
}
cout << f[n+m-1][m][m-1] << endl;
return 0;
}