Sagittarius_L 的博客

Sagittarius_L 的博客

Less is More

LuoguP7074题解

posted on 2020-11-28 21:34:23 | under 题解 |

其实这个题目的dp很好推,不用想复杂了。
我们来观察一下数据,重点是观察小熊每次取数字的规律

看出来什么了吗?没看出来的同学试试画出取数的走向看看。(提示,想想贪吃蛇

观察多组数据你会发现:似乎每组数据中,取数的趋势总是类似蛇形,从左往右取数

这只是巧合吗?不,我们可以尝试验证一下。每次取数字,起点总是 $(0,0)$而重点总是 $(n,m)$,这就导致每次的取数字,一定是从左右选择

那么我们从左到右不妨先让每一个格子从左而来,然后更新从上/下面走过来的最大值,也就是说,我们如果令 $dp[i][j]$为走到这个格子的最大值,我们容易得出: $$dp[i][j] = \max(s, dp[i][j])$$ 其中, $s = max(dp[i][j-1], s) + w[i][j]$。这个 $s$的作用是为了储存从左边到这个点的最大值。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005;
LL dp[N][N];
int n, m, w[N][N];
int main()
{
    cin >> n >> m;
    // 朴素的读入
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> w[i][j];
        }
    }
    memset(dp, -0x3f3f3f3f, sizeof(dp));
    dp[1][0] = 0;
    // 对于每一列开始遍历
    for(int j = 1;j <= m;j ++){
        LL s = -0x3f3f3f3f;
        // 先从上往下
        for(int i = 1;i <= n;i ++){
            s = max(dp[i][j-1], s) + w[i][j];
            dp[i][j] = max(s, dp[i][j]);
        }
        s = -0x3f3f3f3f;
        // 再从下往上
        for(int i = n;i >= 1;i --){
            s = max(dp[i][j-1], s) + w[i][j];
            dp[i][j] = max(s, dp[i][j]);
        }
    }
    cout << dp[n][m];
    return 0;
}