求助! 深搜20pts (悬赏一关注)!!
查看原帖
求助! 深搜20pts (悬赏一关注)!!
486441
13833925596mm楼主2023/1/1 16:40
#include<bits/stdc++.h>
using namespace std;
long long f[1001][1001][4],n,m,a[1001][1001];
long long dfs(int x,int y,int d){
	if(x==1 && y==1 && (d==0 || d==1)) return a[1][1];
	if(x<1 || x>n || y<1 || y>m) return -1e17;
	if(f[x][y][d]!=-1e17) return f[x][y][d];
	if(d==1) f[x][y][d]=max(max(dfs(x-1,y,1),dfs(x-1,y,2)),dfs(x-1,y,3))+a[x][y];
	if(d==2) f[x][y][d]=max(dfs(x,y-1,1),dfs(x,y-1,2))+a[x][y];
	if(d==3) f[x][y][d]=max(dfs(x,y+1,1),dfs(x,y+1,3))+a[x][y];
	return f[x][y][d];
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			f[i][j][1]-=1e17;f[i][j][2]-=1e17;f[i][j][3]-=1e17;
		}
	}
	int x=dfs(n,m,1);
	x=dfs(n,m,2);
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=3;k++){
				cout<<f[i][j][k]<<endl;
			}
			cout<<endl;
		}
		cout<<endl;
	}*/
	cout<<max(f[n][m][1],f[n][m][2]);
	return 0;
}
2023/1/1 16:40
加载中...