记忆化搜索的一些感悟

2018-03-31 20:07:10


例题见luogu1434

记忆化搜索即是在搜索过程中存储搜过的状态,如果接下来再次搜到或遍历到,可以直接调用

代码

#include<cstdio>
#include<cstring>
int max(int x,int y){return x>y?x:y;}
int x,y,maxx=0;
int a[102][102];
int f[102][102];
int X[4]={0,1,0,-1};
int Y[4]={1,0,-1,0};
int dfs(int p,int q)
{
    if(f[p][q])
        return f[p][q];
    for(int i=0;i<=3;i++)
        if(p+X[i]>0&&p+X[i]<=x&&q+Y[i]>0&&q+Y[i]<=y&&a[p][q]<a[p+X[i]][q+Y[i]])
            f[p][q]=max(dfs(p+X[i],q+Y[i]),f[p][q]);
    f[p][q]++;
    if(f[p][q]>maxx)
        maxx=f[p][q];
    return f[p][q];
}
int main()
{
    memset(f,0,sizeof(f));
    scanf("%d%d",&x,&y);
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=x;i++)
        for(int j=1;j<=y;j++)
            f[i][j]=dfs(i,j);
    printf("%d\n",maxx);
    return 0;
}