【记忆化搜索】老鼠吃奶酪

小咪咪 2024-03-26 16:19 35阅读 0赞

**woc，这种DP用记忆化搜索就很好写啊，老师之前说要建图什么的让我一直望而生畏，实际上记忆化一下就好了啊啊啊啊啊啊**

**如果图中不存在环而是个DAG就可以用记忆化搜索写，否则就得手动建图跑最短路**

[4559. 老鼠吃奶酪 - AcWing题库][4559. _ - AcWing]

题意：

![f810d665212836dccbaf40b16040277c.png][]

思路：

因为拓扑序不能通过简单的循环得出，因此需要记忆化搜索一下

感觉在写记忆化的时候和写普通dfs差不多，唯一区别就是要注意我们在这个结点需要维护的是什么东西，然后把维护的东西存在dp数组里就好了，注意dp数组要先初始化

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10;
    
    int n,k;
    int a[mxn][mxn],dp[mxn][mxn];
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    bool check(int x,int y){
        return x>=1&&x<=n&&y>=1&&y<=n;
    }
    int dfs(int x,int y){
        if(dp[x][y]!=-1) return dp[x][y];
        int s=0;
        for(int i=0;i<4;i++){
            for(int j=1;j<=k;j++){
                int vx=x+dx[i]*j,vy=y+dy[i]*j;
                if(check(vx,vy)&&a[x][y]<a[vx][vy]){
                    s=max(s,dfs(vx,vy));
                }
            }
        }
        return dp[x][y]=a[x][y]+s;
    }
    void solve(){
        while(cin>>n>>k&&(n!=-1&&k!=-1)){
            memset(dp,-1,sizeof(dp));
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++) cin>>a[i][j];
            }
            cout<<dfs(1,1)<<'\n';
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[4559. _ - AcWing]: https://www.acwing.com/problem/content/description/4562/
[f810d665212836dccbaf40b16040277c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/943b7a21f8924519849cecf911e560b6.png