题目描述

设有 n×m 的方格图，每个方格中都有一个整数。

现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。

小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

输入格式
第 1 行两个正整数 n,m。

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

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

数据范围
对于 20% 的数据，n,m≤5。
对于 40% 的数据，n,m≤50。
对于 70% 的数据，n,m≤300。
对于 100% 的数据，1≤n,m≤1000。方格中整数的绝对值不超过 104。

输入样例1：
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
输出样例1：
9

样例

输入样例1：
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
输出样例1：
9

算法1

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1500;

int n,m;
int a[N][N];
long long f[N][N][2];

long long getmax(long long a,long long b,long long c)
{
    if(a >= b && a >= c) return a;
    else if(b >= a && b >= c) return b;
    else return c;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    memset(f, 0xcf, sizeof f);
    f[1][0][0] = 0;

    for(int j = 1;j <= m;j ++)
    {
        for (int i = 1; i <= n; i ++ )
            f[i][j][0] = getmax(f[i][j - 1][0], f[i][j - 1][1], f[i - 1][j][0]) + a[i][j];
        for (int i = n; i >= 1; i -- )
            f[i][j][1] = getmax(f[i][j - 1][0], f[i][j - 1][1], f[i + 1][j][1]) + a[i][j];
    }
    printf("%lld",f[n][m][0]);
    return 0;
}