JakeLin

用户名：jake546

访问量：38455

签　名：

腾讯需要我！

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

　　自我简介：

幸福是奋斗出来的

TA的其他文章

【密码】-题解(C++代码) 思路简单
浏览：239

蓝桥杯算法提高VIP-格子位置-题解(C++代码) 带解析
浏览：345

[算法提高VIP]分分钟的碎碎念（C++代码）两种方法：DP与暴力
浏览：404

你可能喜欢

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

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

　　作者: JakeLin　　　　发表时间：2020-03-05 15:35:28 浏览：412　|　评论：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语言训练-立方和不等式（C语言代码）

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

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

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

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

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

评论区

精彩推荐

A+B for Input-Output Practice （C++代码）

简单的a+b （C语言代码）

矩形面积交（C++代码）

Tom数（C语言代码）

大神老白（C语言代码）

一元一次方程（C语言代码）

小O的乘积（C++代码）

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

P1002 （C++代码）

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

JakeLin

TA的其他文章

你可能喜欢

C语言训练-立方和不等式 （C语言代码）

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

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

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

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

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

评论区

精彩推荐

A+B for Input-Output Practice （C++代码）

简单的a+b （C语言代码）

矩形面积交 （C++代码）

Tom数 （C语言代码）

大神老白 （C语言代码）

一元一次方程 （C语言代码）

小O的乘积 （C++代码）

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

P1002 （C++代码）

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

C语言训练-立方和不等式（C语言代码）

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

　　评论区

矩形面积交（C++代码）

Tom数（C语言代码）

大神老白（C语言代码）

一元一次方程（C语言代码）

小O的乘积（C++代码）