60分求助
查看原帖
60分求助
534305
xhd15983640618楼主2022/5/17 16:16
#include<bits/stdc++.h>
using namespace std;

int n,m,a[1001][1001],f[10001][10001][3];

int main( )
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	f[1][1][0]=a[1][1];
	f[1][1][1]=a[1][1];
	f[1][1][2]=a[1][1];
	for(int i=2;i<=n;i++)
	{
		f[i][1][1]=f[i-1][1][1]+a[i][1];
	}
	for(int j=2;j<=m;j++)
	{
		for(int i=1;i<=n;i++)
		{
			if(i!=1)
			{
				f[i][j][1] = max(f[i-1][j][0],f[i-1][j][1]) + a[i][j];
			}
			f[i][j][0] = max(f[i][j-1][0],max(f[i][j-1][1],f[i][j-1][2]) ) + a[i][j];
		}
		for(int i=n-1;i>=1;i--)
		{
			f[i][j][2] = max(f[i+1][j][0],f[i+1][j][2]) + a[i][j];
		}
	}
	cout<<max( f[n][m][0],max(f[n][m][1],f[n][m][2]) );
	return 0;
} 
2022/5/17 16:16
加载中...