求调
查看原帖
求调
1071907
lizihangrq楼主2025/1/21 13:20
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
using namespace std;
const long long N=-0x7ffffffffffff;
long long a[105][105],dp[105][105][2];
int n,m;
long long dfs(int x,int y,int f){
	if(x<1||x>n||y<1||y>m) return N;
	if(x==1&&y==1) return a[1][1];
	if(dp[x][y][f]!=N) return dp[x][y][f];
	if(f){
		dp[x][y][1]=max(dfs(x+1,y,1),max(dfs(x,y-1,0),dfs(x,y-1,1)))+a[x][y];
	}
	else{
		dp[x][y][0]=max(dfs(x-1,y,0),max(dfs(x,y-1,0),dfs(x,y-1,1)))+a[x][y];
	}
	return dp[x][y][f];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j][0]=N;
			dp[i][j][1]=N;
			  scanf("%lld",&a[i][j]);
		}
	}

	printf("%lld\n",dfs(n,m,0));
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cerr<<dp[i][j][0]<<" ";
//		}
//		puts("");
//	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			cerr<<dp[i][j][1]<<" ";
//		}
//		puts("");
//	}	
	return 0;
}
2025/1/21 13:20
加载中...