题解 P7074 【方格取数】

· · 题解

看，€€£出了2000年的原题

如果本题只能向下或向右走的话，做法是显然的，就是一个数字三角形的变体。

但是这题与其它题不一样的是，小熊是可以向上走的。

我在考场上的第一反应就是将 向上、向下、向右 全部分开考虑。

但是考场上脑子短路没推出来？

结果出考场5min想到正解……

我们还是按照刚才的思路，但是简化一下：考虑只向上&向右 或 只向下&向右的最优解。

那么我们对于每一种情况，都可以轻松推出转移方程：

令f[i][j][0]表示第i行j列从上方，右方过来的最优解，f[i][j][1]表示第i行j列从下方，右方过来的最优解。

f(i, j, 0) = \max(f(i-1, j, 0), \max(f(i, j-1, 0), f(i, j-1, 1) ) + a(i, j) f(i, j, 1) = \max(f(i+1, j, 1), \max(f(i, j-1, 0), f(i, j-1, 1) ) + a(i, j)

从下往上走需要倒序扫描

我们发现这里的状态只与上一列的答案有关，于是我们可以用滚动数组的技巧压掉一维。毕竟空间能省就省。

第一列只能从上往下走，亲测必须特判。而最后一列也只能从上往下走，不必特判。

#include <algorithm>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
ll read() {
    register ll n = 0;
    register char ch = getchar();
    bool f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = 0;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        n = (n << 3) + (n << 1) + (ch ^ '0');
        ch = getchar();
    }
    return f ? n : -n;
}
const int N = 1e3 + 5;
ll f[N][2], dp[N], a[N][N];
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = read();
    // 第一列不存在像上走的情况，必须特判
    dp[1] = a[1][1];
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + a[i][1];
    for (int j = 2; j <= m; j++) {
        // 因为有负数，所以需要设定边界初始值
        f[1][0] = dp[1] + a[1][j], f[n][1] = dp[n] + a[n][j];
        // 状态转移
        for (int i = 2; i <= n; i++)
            f[i][0] = max(dp[i], f[i - 1][0]) + a[i][j];
        for (int i = n - 1; i >= 1; i--)
            f[i][1] = max(dp[i], f[i + 1][1]) + a[i][j];
        // 滚动数组
        for (int i = 1; i <= n; i++)
            dp[i] = max(f[i][0], f[i][1]);
    }
    // 最后一行是不能向上走的，只考虑向下的情况
    printf("%lld\n", f[n][0]);
    return 0;
}