acwing 275 传纸条 (线性dp)

#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 ;
}