JakeLin

用户名：jake546

访问量：43185

签　名：

腾讯需要我！

等　　级
排　　名	40
经　　验	13199
参赛次数	3
文章发表	85
年　　龄	21
在职情况	学生
学　　校	华南农业大学
专　　业

　　自我简介：

幸福是奋斗出来的

TA的其他文章

JakeLin-题解1923：蓝桥杯算法提高VIP-学霸的迷宫（C++代码）
浏览：681

迷宫问题-题解(C/C++)-BFS（附图详细解析）
浏览：1652

JakeLin-题解1426：蓝桥杯历届试题-九宫重排（C++代码）
浏览：536

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

JakeLin-题解1436：蓝桥杯2014年第五届真题-地宫取宝（C++代码）

　　作者: JakeLin　　　　发表时间：2020-03-05 15:35:28 浏览：426　|　评论：1　

原题链接：蓝桥杯2014年第五届真题-地宫取宝

一、DFS深搜法：
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 55;
const LL Q = 1000000007;
int map[maxn][maxn];
int dx[] = {0,1};
int dy[] = {1,0}; 
int n,m,k;
int cnt=0;
void dfs(int x,int y,int num,int maxValue){ 
	if(x==n && y==m) { //到达出口 
		if(num==k || (num==k-1 && map[x][y]>maxValue)){
			cnt=(cnt+1)%Q;
		}
	} 
	for(int i=0;i<2;i++){ //两个方向
		int newx = x + dx[i];
		int newy = y + dy[i];
		if(newx<=n && newy<=m){ //取和不取两种情况相加 
			if(map[x][y] > maxValue){
				dfs(newx,newy,num+1,map[x][y]); //取（x，y） 
			}
			dfs(newx,newy,num,maxValue);  //不取 （x，y） 
		}
	}
}
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,0,-1);
	cout<<cnt;
	return 0;
}

```
部分数据超时，需另外想办法：
**记忆搜索：dp+深搜**
思路是用dp[x][y][num][maxValue]记录DFS的返回值，若后续重新访问到这种状态则可直接取值，不需重复访问
```cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 55;
const LL Q = 1000000007;
int map[maxn][maxn];
int treasure[maxn];
int dx[] = {0,1};
int dy[] = {1,0}; 
LL dp[maxn][maxn][maxn][maxn];
//dp[x][y][num][maxvalue]:
//走到(x,y)位置(还没选入) 手中num个宝贝 最大值maxValue 的！方！案！数！ 
int n,m,k;
LL dfs(int x,int y,int num,int maxValue){ 
   //走到(x,y)位置  手中已拿num个宝贝 手中宝贝最大值maxValue 
   //这个方法进来就是为了求 dp[x][y][num][maxvalue]，并返回它，好吗！ 
	if(dp[x][y][num][maxValue+1]!=-1){ 
	//只是记忆搜索加速处理，已经知道了dp就不用重复求了 
		return dp[x][y][num][maxValue+1];
	}
	if(x==n && y==m) { //到达出口 
		if(num==k || (num==k-1 && map[x][y]>maxValue)){
			dp[x][y][num][maxValue+1] = 1;
			return 1;  //1个方案成立 
		}else{
			dp[x][y][num][maxValue+1] = 0;
			return 0;  //不成立返回0 后面s要叠加的 
		}
	} 
	LL s=0; //此刻 dp[x][y][num][maxvalue]的方案数 
	for(int i=0;i<2;i++){
		int newx = x + dx[i];
		int newy = y + dy[i];
		if(newx<=n && newy<=m){ //取和不取两种情况相加 
			if(map[x][y] > maxValue){
				s += dfs(newx,newy,num+1,map[x][y])%Q; //取（x，y） 
			}
			s += dfs(newx,newy,num,maxValue)%Q;  //不取 （x，y） 
		}
	}
	dp[x][y][num][maxValue+1] = s%Q; //此刻 dp[x][y][num][maxvalue]的方案数求出了 
	return s%Q;
}
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(dp,-1,sizeof(dp)); 
	dfs(1,1,0,-1);
	cout<<dp[1][1][0][0];
	return 0;
}

```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

沐白

为啥输出是dp[1][1][0][0]，不是dp[n][m][k][...]

2020-03-14 21:36:30

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

JakeLin-题解1436：蓝桥杯2014年第五届真题-地宫取宝（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

printf基础练习2 （C语言代码）

不容易系列（C语言代码）

用筛法求之N内的素数。（C语言代码）

WU-格式化数据输出（C语言代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

蚂蚁感冒（C语言代码）

字符逆序（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

JakeLin

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

JakeLin-题解1436：蓝桥杯2014年第五届真题-地宫取宝 （C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

printf基础练习2 （C语言代码）

不容易系列 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

WU-格式化数据输出 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

蚂蚁感冒 （C语言代码）

字符逆序 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

JakeLin-题解1436：蓝桥杯2014年第五届真题-地宫取宝（C++代码）

　　评论区

不容易系列（C语言代码）

用筛法求之N内的素数。（C语言代码）

WU-格式化数据输出（C语言代码）

用筛法求之N内的素数。（C语言代码）

蚂蚁感冒（C语言代码）

字符逆序（C语言代码）