可爱萌新刚学OI,记搜在线求调
查看原帖
可爱萌新刚学OI,记搜在线求调
1002529
Fp0cY1tZ6Nn4Rd_楼主2024/7/17 09:30
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1005,inf=0x7fffffff;
int a[N][N],dp[N][N],n,m,ans;
int dir[3][2]={{0,1},{1,0},{-1,0}};
int vis[N][N];
int dfs(int x,int y,int sum){
	if(x==n&&y==m) return max(vis[x][y],sum+a[x][y]);
	if(vis[x][y]) return vis[x][y];
	for(int i=0;i<3;i++){
		int dx=x+dir[i][0],dy=y+dir[i][1];
		if(dx>=1&&dx<=n&&dy>=1&&dy<=m)
			vis[x][y]=max(vis[x][y],dfs(dx,dy,sum+a[dx][dy]));
	}
	return vis[x][y];
}
int main(){
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
	ios::sync_with_stdio(false);
	memset(vis,0xbf,sizeof(vis));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	}
	vis[1][1]=true;
	ans=dfs(1,1,0);
	cout<<ans<<endl;
	return 0;
}
2024/7/17 09:30
加载中...