题解 P7074 【方格取数】

· · 题解

算法选择：

直接看数据范围好吧，n\leq 10^3,显然DFS不可做。众所周知，大部分的递归都可以转换为递推，而递推复杂度显然是小于递归的。

(递归 O(3^{m+n}),递推(n \times m))(不对请指正)

所以这题我们选择动态规划

转移方程：

如果这题只有右、下的走法的话，那么这题绝对是道水题，难就难在还可以往上走。所以我们可以将这三种走法分开处理，分为右、上一种走法和右、下一种走法。

定义一个数组 f[1001][1001][2] 前两维分别对应坐标 x,y。

f[x][y][0]指，走到x,y时,从右、下这种走法推出的最大值。

f[x][y][1]指，走到x,y时,从右、上这种走法推出的最大值。

所以可以轻易得到方程

f[j][i][0]=max(f[j][i-1][0],max(f[j][i-1][1],f[j-1][i][0]))+a[j][i];//因为两种走法都可以向右走，所以对于左边的格子，是从0还是1哪种走法推来的并不重要

f[j][i][1]=max(f[j][i-1][0],max(f[j][i-1][1],f[j+1][i][1]))+a[j][i];

细节处理：

1.相信细心的同学已经看出，上面的转移方程好像有什么不对劲，i和j的位置好像与平常的题目不太一样。这就是一个小坑了，我们知道，可以向上走和向下走，所以，肯定是推出当前列的最佳走法，再向右拓展。

所以循环进行状态转移的时候，得先循环列，再循环行。

2.因为最右下那格是不可能由上这种走法推导出来，而向右移动的走法又已经被右、下这种方法包括，所以最后输出的应该是f[n][m][0]。

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll f[1002][1002][2],a[1002][1002];
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            scanf("%lld",&a[i][j]);
        }
    }
    memset(f,128,sizeof(f));
    f[1][1][0]=a[1][1];
    for(ll i=1;i<=m;i++){
        for(ll j=1;j<=n;j++){
            if(i==1&&j==1) continue;
            f[j][i][0]=max(f[j][i-1][0],max(f[j][i-1][1],f[j-1][i][0]))+a[j][i];
        }
        for(ll j=n;j>=1;j--){
            f[j][i][1]=max(f[j][i-1][0],max(f[j][i-1][1],f[j+1][i][1]))+a[j][i];
        }
    }
    printf("%lld",f[n][m][0]);
    return 0;
}