题目描述
设有 n×m 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。
输入格式
第一行有两个整数 n,m。
接下来 n 行每行 m 个整数，依次代表每个方格中的整数。
输出格式
一个整数，表示小熊能取到的整数之和的最大值。
输入输出样例
输入 #1复制
3 4 1 -1 3 2 2 -1 4 -1 -2 2 -3 -1输出 #1复制
9输入 #2复制
2 5 -1 -1 -3 -2 -7 -2 -1 -4 -1 -2输出 #2复制
-10说明/提示
样例 1 解释
样例 2 解释
数据规模与约定
- 对于 20% 的数据，n,m≤5。
- 对于 40% 的数据，n,m≤50。
- 对于 70% 的数据，n,m≤300。
- 对于 100% 的数据，1≤n,m≤103。方格中整数的绝对值不超过 104。
#include<bits/stdc++.h> using namespace std; const int N=1e3+10; typedef long long LL; LL f[N][N]; LL g[N][N]; LL a[N][N]; 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]; } } memset(f,-0x3f,sizeof f); memset(g,-0x3f,sizeof g); f[0][1]=0; for(int j=1;j<=m;j++) { for(int i=1;i<=n;i++) { f[i][j]=max(f[i-1][j],max(f[i][j-1],g[i][j-1]))+a[i][j]; } for(int i=n;i>=1;i--) { g[i][j]=max(g[i+1][j],max(f[i][j-1],g[i][j-1]))+a[i][j]; } } cout<<f[n][m]<<endl; return 0; }
