90大佬求调
查看原帖
90大佬求调
917506
YaoTianYu楼主2023/10/15 12:08
#include<bits/stdc++.h>
using namespace std;
int n,m,maxn=0,cnt=0;
#define inf 10000000000ll
long long sum=0;
long long dx[5]={0,1,-1};
long long dy[5]={1,0,0};
long long map2[1005][1005]={}; 
void maxs(long long &a,long long b)
{
	a=max(a,b);
}
long long dp[1005][1005][2]={};
int dfs(int x,int y,int k)
{
	long long ans=-inf;
	if(x==1&&y==1)
	{
		dp[x][y][0]=map2[x][y];
		return map2[x][y];
	}
	if(dp[x][y][k]!=-inf)
	{
		return dp[x][y][k];
	}
	if(y>1)
	{
		maxs(ans,dfs(x,y-1,0)+map2[x][y]);
		maxs(ans,dfs(x,y-1,1)+map2[x][y]);
	}
	if(k)
	{
		if(x>1)
		{
			maxs(ans,dfs(x-1,y,1)+map2[x][y]);
		}
	}
	else
	{
		if(x<n) maxs(ans,dfs(x+1,y,0)+map2[x][y]);
	}
	dp[x][y][k]=ans;
	return ans;
}
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>map2[i][j];
			dp[i][j][0]=dp[i][j][1]=-inf;
		}
	}
	cout<<dfs(n,m,1);
	







 } 
2023/10/15 12:08
加载中...