蒟蒻求助(35分)
查看原帖
蒟蒻求助(35分)
304211
精神小伙!楼主2021/10/5 12:20
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll INF=1000000000; 
const int maxn=1001;
int a[maxn][maxn],n,m;
ll down[maxn][maxn];
ll up[maxn][maxn];
ll dp[maxn][maxn];
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<=m;++i)
        down[0][i]=up[n+1][i]=INF;
	for(int i=2;i<=n;++i)
	    dp[i][0]=-INF;
	for(int j=1;j<=m;++j)
	{
		for(int i=1;i<=n;++i)
		    down[i][j]=max(down[i-1][j],dp[i][j-1])+a[i][j];
		for(int i=n;i>=1;--i)
		    up[i][j]=max(up[i+1][j],dp[i][j-1])+a[i][j];
		for(int i=1;i<=n;++i)
		    dp[i][j]=max(down[i][j],up[i][j]);
	}	
	cout<<dp[n][m]-INF<<endl;
	return 0;
}
2021/10/5 12:20
加载中...