95pts求助
查看原帖
95pts求助
107843
Citrine楼主2020/11/12 17:33

第16个点WA了

#include <cstdlib>
#include <cstdio>
using namespace std;
int dp[1005][1005][5]={};
int fl[1005][1005][5]={};
int mp[1005][1005]={};
int n,m;
const int inf=-0xffffff;
inline int max(int a,int b)
{
	return a>b?a:b;
}
inline int dfs(int x,int y,int k)
{
	if (fl[x][y][k]==1)
	{
		return dp[x][y][k];
	}
	if (k==1)
	{
		dp[x][y][k]=max(dfs(x+1,y,0),dfs(x+1,y,1))+mp[x][y];
	}
	if (k==2)
	{
		dp[x][y][k]=max(dfs(x-1,y,0),dfs(x-1,y,2))+mp[x][y];
	}
	if (k==0)
	{
		dp[x][y][k]=max(max(dfs(x,y-1,0),dfs(x,y-1,1)),dfs(x,y-1,2))+mp[x][y];
	}
	fl[x][y][k]=1;
	return dp[x][y][k];
}
int main()
{
	scanf("%d %d",&n,&m);
	n++,m++;
	for (register int i=0;i<=n;i++)
	{
		for (register int j=0;j<=m;j++)
		{
			mp[i][j]=inf;
		}
	}
	for (register int i=1;i<n;i++)
	{
		for (register int j=1;j<m;j++)
		{
			scanf("%d",&mp[i][j]);
		}
	}
	for (register int i=0;i<=n;i++)
	{
		for (register int j=0;j<=m;j++)
		{
			if (mp[i][j]==inf)
			{
				dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=inf;
				fl[i][j][0]=fl[i][j][1]=fl[i][j][2]=1;
			}
		}
	}
	dp[1][1][0]=dp[1][1][1]=dp[1][1][2]=mp[1][1];
	fl[1][1][0]=fl[1][1][1]=fl[1][1][2]=1;
	printf("%d",max(dfs(n-1,m-1,0),dfs(n-1,m-1,2)));
	return 0;
}
2020/11/12 17:33
加载中...