题目描述

最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。
奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为(R,C)的馅饼旁边停止走动。每做一次移动，你必须走到下一列的某块馅饼旁边，并且，行数的变动不能超过1（也就是说，如果现在你站在坐标为(r,c)的馅饼边上，下一步你可以走到坐标为(r-1,c+1),(r,c+1),或者(r+1,c+1)的馅饼旁边）。当你从一块馅饼边经过，你就可以拿走馅饼里所有的金币。当然啦，你一定不会愿意因半路离开草地而失去唾手可得的金币，但，最终你一定得停在坐标为(R,C)的馅饼旁边。
现在，你拿到了一张标记着馅饼矩阵中，每一块馅饼含金币数量的表格。那么，按照规则，你最多可以拿到多少金币呢？

思路

做题时看着数据范围感觉爆搜顺便减下枝（觉得能过的(●ˇ∀ˇ●)...）应该能过，最后只过了70%。。。，然后看了一下大佬的们的题解，都是Dp，所以就参考了一下自己也尝试了一下终于过了。。。

其实Dp的话就很好想了，先确定状态f[i][j]表示从(1,1)走到(i,j)能拾取到的金币数量最大值。

1.那么根据题意不难看出，想要走到(i,j)这个点，只有三种方式，分别是从(i-1,j-1)、(i,j-1)、(i+1,j-1)走过来。

2.通过草稿一下很容易就可以看出，我们是不能走到Σ(i,i)这条线一下的点的，并且当r-i>c-j时最终是走不到(r,c)的，所以如果有想法的大佬（觉得能爆搜+剪枝过的）求教＞︿＜

3.之后就是推一下状态转移方程了，都说到这了肯定能推出来了吧。。＞︿＜
f[i][j] = max(f[i-1][j-1],f[i][j-1],f[i+1][j-1]) + a[i][j] (需要注意的是只有当前点能走到才去加上这个点的金币值);

4.对了需要注意的是我们想求f[i][j]这个状态是需要知道f[i-1][j-1],f[i][j-1],f[i+1][j-1]的，所以在for循环枚举的时候要从左下角的点开始枚举并且是从下到上求解的，具体为什么大家草稿一下就清晰了。

Code

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 110;
int a[N][N], f[N][N], n, m;

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]);

    for(int i = 1; i <= m; i ++ )
        for(int j = n; j >= 1; j -- )
        {
            if(n - j > m - i || j > i) continue;   //先判断一下当前点是否能走并且 是否能走到(r,c)  （1）
            f[j][i] = max(f[j - 1][i - 1], f[j][i - 1]);
            f[j][i] = max(f[j + 1][i - 1], f[j][i]);
            f[j][i] += a[j][i];
        }

    printf("%d\n", f[n][m]);

    return 0;
}