CH5103 275. 쪽지를 돌리다

단계: 총 n+m-2단계
유지보수 상태: 두 경로 이동 i단계 후 끝의 좌표
이렇게 하면 모두 5차원, nmnm*(n+m-2), 적합하지 않다
우리는 경로 세로 좌표가 시종 보수 +2-가로 좌표와 같다는 것을 발견했다
그래서 2차원을 생략했다
만약 스크롤 그룹이 1차원을 더 절약할 수 있다면, 필요 없습니다
 

#include 
using namespace std;
typedef long long ll;
//typedef __int128 LL;
//typedef unsigned long long ull;
//#define F first
//#define S second
typedef long double ld;
typedef pair pii;
typedef pair pll;
typedef pair pdd;
const ld PI=acos(-1);
const ld eps=1e-9;
//unordered_mapmp;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const int seed=131;
const int M = 1e5+7;
int f[103][53][53];//f[i][x1][x2]   i  ，        
//    ： y1=i-x1,y2=i-x2; 
//           ，      ， 4  
int a[57][57];
int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
  	int n,m;
  	cin>>n>>m;
  	for(int i=1;i<=n;i++)
  	for(int j=1;j<=m;j++)
  	{
  		cin>>a[i][j];
	}
	f[0][1][1]=a[1][1];
	for(int i=0;i<=n+m-2;i++)
  	for(int x1=1;x1<=min(n,i+1);x1++)
  	for(int x2=1;x2<=min(n,i+1);x2++)
  	{
  		//       2 50   ，    ，     
  	//	if(i+3-x1>0&&i+3-x2>0)
  		f[i+1][x1][x2]=max(f[i+1][x1][x2],f[i][x1][x2]+((x1==x2)?a[x1][i+3-x1]:(a[x1][i+3-x1]+a[x2][i+3-x2])));
  		//    
  		//if(i+3-x1>0&&i+3-x2-1>0)
  		f[i+1][x1][x2+1]=max(f[i+1][x1][x2+1],f[i][x1][x2]+((x1==x2+1)?a[x1][i+3-x1]:(a[x1][i+3-x1]+a[x2+1][i+3-x2-1])));
  		//    
  	//	if(i+3-x1-1>0&&i+3-x2>0)
  		f[i+1][x1+1][x2]=max(f[i+1][x1+1][x2],f[i][x1][x2]+((x1+1==x2)?a[x2][i+3-x2]:(a[x1+1][i+3-x1-1]+a[x2][i+3-x2])));
  		//    
  	//	if(i+3-x1-1>0&&i+3-x2-1>0)
  		f[i+1][x1+1][x2+1]=max(f[i+1][x1+1][x2+1],f[i][x1][x2]+((x1+1==x2+1)?a[x1+1][i+3-x1-1]:(a[x1+1][i+3-x1-1]+a[x2+1][i+3-x2-1])));
  		//    
	}
	cout<