75pts求调,5WA
查看原帖
75pts求调,5WA
1209094
lpk1118楼主2024/10/18 23:17
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1005][1005],u[1005][1005],d[1005][1005],l[1005][1005],ans[1005][1005];
signed main()
{
	memset(u,INT_MIN,sizeof(u));
	memset(d,INT_MIN,sizeof(d));
	memset(l,INT_MIN,sizeof(l));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
    ans[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        ans[i][1]=u[i][1]=ans[i-1][1]+a[i][1];
	for(int j=2;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
            l[i][j]=ans[i][j-1]+a[i][j];
        for(int i=2;i<=n;i++)
            u[i][j]=max(u[i-1][j],l[i-1][j])+a[i][j];
        for(int i=n-1;i>=1;i--)
            d[i][j]=max(d[i+1][j],l[i+1][j])+a[i][j];
        for(int i=1;i<=n;i++)
            ans[i][j]=max(l[i][j],max(d[i][j],u[i][j]));
    }
	cout<<ans[n][m];
	return 0;
}

u记录的是从上方来的,d记录的是从下方来的,l记录的是从左侧来的

2024/10/18 23:17
加载中...