自动搬运

查看原文

来自洛谷，原作者为

	_cpp lraaug

搬运于2025-08-24 22:40:41，当前版本为作者最后更新于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;
}