55求调
查看原帖
55求调
739214
dmx7u19x楼主2024/1/2 13:06
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
	ll on;//从上面来的值 
	ll left;//从左边来的值 
	ll under;//从下面来的值 
	ll h;//自己的结果 
}dp[1010][1010];
ll a[1010][1010];
ll n,m;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)dp[i][1].left=INT_MIN;
	for(int i=1;i<=m;i++)dp[n][i].under=INT_MIN;
	for(int i=1;i<=m;i++)dp[1][i].on=INT_MIN;
	dp[1][1].on=INT_MIN;
	dp[1][1].h=a[1][1];
	for(int j=1;j<=m;j++)
	{
		for(int i=1;i<=n;i++)//更新上面来的值  
		{
			if(dp[i][j].left==INT_MIN&&dp[i][j].on==INT_MIN)dp[i+1][j].on=a[i][j];
			else dp[i+1][j].on=max(dp[i][j].left,dp[i][j].on)+a[i][j];
		}
		if(j!=1)
		{
			for(int i=n;i>1;i--)//更新从下面来的值  
			{
				if(dp[i][j].under==INT_MIN&&dp[i][j].left==INT_MIN)dp[i+1][j].on=a[i][j];
				else dp[i-1][j].under=max(dp[i][j].left,dp[i][j].under)+a[i][j];
			}
		}
		for(int i=1;i<=n;i++)
		{
			dp[i][j].h=max(max(dp[i][j].on,dp[i][j].under),dp[i][j].left)+a[i][j];//更新自己的结果
			if(j+1<=m)dp[i][j+1].left=dp[i][j].h;//更新左边来的值 
		}
	}
	cout<<dp[n][m].h;	
	return 0;
}
2024/1/2 13:06
加载中...