题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1

输出 #1

9

输入输出样例 #2

输入 #2

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

输出 #2

-10

说明/提示

样例 1 解释

样例 2 解释

数据规模与约定

• 对于 $20\%$ 的数据，$n, m \le 5$。
• 对于 $40\%$ 的数据，$n, m \le 50$。
• 对于 $70\%$ 的数据，$n, m \le 300$。
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^3$。方格中整数的绝对值不超过 $10^4$。

定义$sh[i][j]$为在第$j$列中，路径从该列的‌上方‌最终到达$(i,j)$ 时的最大和。

定义‌$x[i][j]$为在第$j$列中，路径从该列的‌下方‌最终到达$(i,j)$时的最大和。

定义$dp[i][j]$为到达坐标$(i,j)$时，所能获得的‌最大和。

for(int i=1;i<=n;i++) s+=a[i][1],dp[i][1]=s,sh[i][1]=MINN,xi[i][1]=s;

特殊:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e3+5,MINN=INT_MIN;
ll s,dp[MAXN][MAXN],a[MAXN][MAXN],sum,sh[MAXN][MAXN],xi[MAXN][MAXN],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++) s+=a[i][1],dp[i][1]=s,sh[i][1]=MINN,xi[i][1]=s;//初始化
	for(int j=2;j<=m;j++){
		for(int i=1;i<=n;i++) sum=dp[i][j-1],sum=(i>1 ? max(sum,sh[i-1][j]):dp[i][j-1]),sh[i][j]=sum+a[i][j];
		for(int i=n;i>=1;i--) sum=dp[i][j-1],sum=(i<n ? max(sum,xi[i+1][j]):dp[i][j-1]),xi[i][j]=sum+a[i][j];
		for(int i=1;i<=n;i++) dp[i][j]=max(sh[i][j],xi[i][j]);
	}
	cout<<dp[n][m];
	return 0;
}
//fish code