f[i][x1][x2] 表示 走了 i 步 第一条路径 1，1 从走到 （x1, i - x1） 走了 i 步 第二条路径走到（x2,k-x2） 的最大值
我们对于x1 x2 的遍历取值要有范围
#include<iostream> #include<algorithm> #include<cstring> using namespace std ; const int N = 55 ; int f[N*2][N][N] ; int w[N][N] ; int n , m ; int main(){ cin >> n >> m ; for(int i = 1 ; i <= n ; i ++){ for(int j = 1 ; j <= m ; j ++){ cin >> w[i][j] ; } } f[2][1][1] = w[1][1] ; for(int i = 2 ; i <= n + m ; i ++){ for(int j = max(1,i-m) ; j <= n && j < i; j ++){ for(int k = max(1,i-m) ; k <= n && k < i ; k++){ for(int a = 0 ; a <= 1 ; a ++){ for(int b = 0 ; b <= 1 ; b ++){ int t = w[j][i-j] ; if(j != k || i== 2 || i== m + n ){ t += w[k][i-k] ; } f[i][j][k] = max(f[i][j][k] , f[i-1][j-a][k-b] + t) ; } } } } } cout << f[m+n][n][n] << endl ; }
