P8612 题解

_cpp · 2022-10-29 22:52:25 · 题解

这题考查我们对记忆化搜索的掌控。

Code 1：

首先，暴力搜索。对于任何一个点，都有四种状态，分别是：向右走，不拿；向下走，不拿；向右走，拿；向下走，拿。只要分别搜索这四个状态，再加边界值。，我们的第一份暴力代码就完成了。注意，还有一个特判。那就是终点前有两种状态，一种为不拿终点格子中的宝物，并且手上的宝物正好为 k 件。还有一种是到终点了，手上只有 k-1 件宝物，并且终点格子中的宝物价值比小明手中任意宝贝价值都大，那也可以算一种方案。预计得分60。

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int n,m,k;
int map[59][59];
int ans=0;
void dfs(int x, int y, int maxV, int num){
    if(x==n+1 || y==m+1)    return;  //边界
    if(x==n && y==m){    //到终点了
        if(num==k || num==k-1&&map[x][y]>maxV){
            ans++; //到终点前有两种状态
        }
        ans %= MOD;  //注意取模
        return;
    }
    dfs(x,y+1,maxV,num);
    dfs(x+1,y,maxV,num);
    if(map[x][y] > maxV){
        dfs(x,y+1,map[x][y],num+1);
        dfs(x+1,y,map[x][y],num+1); //四种状态的搜索
    }
}
int main(){
    cin >> n >> m >> k;
    for( int i=1; i<=n; i++ )
        for( int j=1; j<=m; j++ ) cin >> map[i][j];
    dfs(1,1,-1,0); //注意，一开始最大值要为-1
    cout << ans;
    return 0;
}

Code 2：

要想拿到满分，就要用记忆化搜索。简单来说，就是拿一个 cache 数组分四维，分别记录上面说过的四种状态。如果有之前算过的值，那就直接返回，如没有，就算，算好后再存入数组中。

#include<bits/stdc++.h> 
using namespace std;
const int MOD = 1000000007;
int cache[59][59][14][14],Map[59][59],n,m,k; 
int dfs(int x, int y, int maxV, int num){
    if(x==n+1 || y==m+1) return 0;  //边界
    if(cache[x][y][maxV+1][num] != -1){
        return cache[x][y][maxV+1][num]; //如果有值了，就直接返回
    }
    long long res=0;
    if(x==n && y==m){
        if(num==k || num==k-1&&Map[x][y]>maxV){
            res++;  //到终点了
        }
    }else{   
        res += dfs(x,y+1,maxV,num);  //计算四种状态
        if(Map[x][y] > maxV){
            res += dfs(x,y+1,Map[x][y],num+1);
        }
        res += dfs(x+1,y,maxV,num);
        if(Map[x][y] > maxV){
            res += dfs(x+1,y,Map[x][y],num+1);
        }   
    } 
    cache[x][y][maxV+1][num] = res % MOD;  //储存运算结果
    return cache[x][y][maxV+1][num];  //返回
}
int main()
{
    cin >> n >> m >> k;
    for( int i=1; i<=n; i++ )
        for( int j=1; j<=m; j++ ) cin >> Map[i][j];
    memset(cache,-1,sizeof(cache));  //注意要初始化为-1
    cout << dfs(1,1,-1,0);
    return 0;
}