w_w
  • 板块学术版
  • 楼主tjx123456
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/9/25 20:39
  • 上次更新2024/9/25 22:38:49
查看原帖
w_w
1180981
tjx123456楼主2024/9/25 20:39
#include <cstdio>
const int maxn=1005;
const int dx[]={0,1,-1},dy[]={1,0,0};
bool hasmem[maxn][maxn];
int mem[maxn][maxn];
int a[maxn][maxn];
int n,m;
bool is_valid(int x,int y){
	if(x<1||x>n||y<1||y>m) return false;
	return true;
}
int dfs(int x,int y,long long sum){
	if(x==n&&y==m) return 0;
	if(mem[x][y]>=0||hasmem[x][y]) return mem[x][y];
	long long ans=0;
	for(int i=0;i<3;i++){
		int t=dfs(x+dx[i],y+dy[i],0)+a[x+dx[i]][y+dy[i]];
		sum+=t;
	}
	if(sum>ans) ans=sum;
	hasmem[x][y]=true;
	mem[x][y]=ans;
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			scanf("%d",&a[x][y]);
			hasmem[x][y]=false;
			mem[x][y]=-1;
		}
	}
	printf("%d\n",dfs(1,1,0));
	return 0;
}
2024/9/25 20:39
加载中...