P1508 Likecloud-吃、吃、吃

· · 题解

打倒DP暴政，世界属于记搜！

虽然我不知道怎么回事这道题用记搜比DP慢就是了

这道题有个小坑点：有负数点（而且必须吃），所以如果一开始把记忆数组f赋值成-1就会挂。如果是DP就会WA,鬼知道为什么用记搜就会RE。

代码:

#include<bits/stdc++.h>
using namespace std;
int a[202][202];
int f[202][202];
bool vis[202][202];//存放这个点有没有访问过
int n,m;
int my_max(int x,int y,int z)//三个数比较大小
{
    int ans=x;
    if (ans<y) ans=y;
    if (ans<z) ans=z;
    return ans;
}
int dfs(int x,int y)
{
    if (vis[x][y]) return f[x][y];
    for(int i=-1;i<=1;i++)
    {
        if ((y+i>0)&&(y+i<=n)&&(x-1>0))f[x][y]=max(f[x][y],dfs(x-1,y+i)+a[x][y]);//记忆化
    }
    vis[x][y]=true;
    return f[x][y];
}
int main()
{
    cin>>n>>m;
    memset(a,-9999,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    memset(f,-0x3f,sizeof(f));//初始化
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=m;i++) f[1][i]=a[1][i],vis[1][i]=true;//第一排都无法再向下搜索了
    dfs(n+1,m/2+1);
    cout<<my_max(f[n][m/2],f[n][m/2+1],f[n][m/2+2])<<endl;//答案只有可能在这三个点里
    return 0;
}
//code by ちゃん