题解 P7074 【方格取数（民间数据）】

· · 题解

宣传一波博客：传送门

为什么大家都是dp啊，我只会写记忆化搜索。。。

题目简洁明了，考场上看完这道题后我想到了这道题： n * m 的网格中，小熊从左上角走到右下角，只能向右或向下走，每个格子有权值 a_{i,j}，求出一条路径使路上权值和最大。（大家应该都做过）

转移方程 （我竟然用了dp） ：f_{i,j}=\max{(f_{i-1,j},f_{i,j-1})+a_{i,j}}

这道题只是多加了一个向上的方向，但是二维就不能计算了。

怎么办？直接加一维方向！

由于我用的是记忆化搜索，这里写一下思路：

首先， dfs 内设 3 个参数 x,y,dis（我为什么会用 dis ???），表示走到 (x,y) （注意是第 x 行 y 列 而不是坐标系中的 (x,y)）时怎么走过来的。 dis=0 表示向下走， dis=1 表示向上走， dis=2 表示这个点是这一列第一个被走到的点，想走哪里就走哪里。

由于每一个方格只能经过一次，因此一旦这一列的路径方向定了就不能改变。

搜索时：

令 ans 表答案：

这种程度的搜索相信各位都想的出来，接下来加上记忆化数组 f 就可以完美 AC 了！

当然，友情提醒一句：

int 一时爽，溢出火葬场!

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1000+10;
const long long Min=-1e18,Minn=-1e17;
int n,m,a[MAXN][MAXN];
long long f[MAXN][MAXN][5];

long long Max(long long fir,long long sec)
{
    if(fir>sec) return fir;
    return sec;
}//最好手打max

long long dfs(int x,int y,int dis)
{
    long long ans=Min;//初始化成为-1e18(注意，答案也有可能是负数，样例2中有详细说明)
    if(x==1&&y==1) return a[1][1];//边界条件的处理
    if(x<1||y<1||x>n||y>m) return Min;
    if(f[x][y][dis]>Minn) return f[x][y][dis];
    if(dis==2)
    {
        ans=Max(ans,Max(dfs(x,y-1,2),Max(dfs(x+1,y,0),dfs(x-1,y,1)))+(long long)a[x][y]);
        //万一f[x][y][dis]>Min但是实际上并不是答案我们不就被坑了？所以以-1e17作为参照标准
    }
    else
    {
        ans=Max(ans,dfs(x,y-1,2)+(long long)a[x][y]);
        if(dis==0)
        {
            ans=Max(ans,dfs(x+1,y,0)+(long long)a[x][y]);
        }
        else
        {
            ans=Max(ans,dfs(x-1,y,1)+(long long)a[x][y]);
        }
    }
    return f[x][y][dis]=ans;
}

int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    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<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j][0]=f[i][j][1]=f[i][j][2]=Min;//初始化
    cout<<dfs(n,m,2)<<"\n";//采取倒着搜的模式
    return 0;
}

总结：

CSP-J 的 dp 题都能用记忆化搜索写，既然我们会爆搜，加记忆化又很简单，所以我们为什么不写记忆化搜索呢？

如果想写 dp 转移方程的，可以参照其他大佬的题解。（其实上面代码改一下就出来了qwq）