题目描述

设有 n×m?的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

输入格式

第一行有两个整数?n,m。

接下来?n?行每行?m?个整数，依次代表每个方格中的整数。

输出格式

一个整数，表示小熊能取到的整数之和的最大值。

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2

输出 #2复制

-10

说明/提示

样例 1 解释

样例 2 解释

题解：

题解博主随后会更新

Ac code:?

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[1001][1001];
long long up[1005],down[1005],f[1005];
inline int read(){
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		a[i][j]=read();
	f[1]=a[1][1];
	for(int i=2;i<=n;i++) f[i]=f[i-1]+a[i][1];
	for(int j=2;j<m;j++){
		memset(down,0,sizeof(down));
		memset(up,0,sizeof(up));
		down[1]=f[1]+a[1][j];up[n]=f[n]+a[n][j];
		for(int i=2;i<=n;i++) down[i]=max(f[i],down[i-1])+a[i][j];
		for(int i=n-1;i>=1;i--) up[i]=max(f[i],up[i+1])+a[i][j];
		for(int i=1;i<=n;i++) f[i]=max(down[i],up[i]);
	}
	f[1]+=a[1][m];
	for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1])+a[i][m];
	printf("%lld",f[n]);
	return 0;
}