czy123

用户名：czy0211

访问量：5146

签　名：

专注是大脑一直想着你要做的事。

等　　级
排　　名	1534
经　　验	2804
参赛次数	1
文章发表	13
年　　龄	0
在职情况	学生
学　　校	NCWU
专　　业

　　自我简介：

做一个人，不悔旧历史，不惧新事物，不纠结过往，不害怕将来，一切积极面对，凡事皆不乱于心，如此，一切安好。

TA的其他文章

采药-题解(C++代码)
浏览：198

蓝桥杯算法训练VIP-方格取数-题解(C++代码)
浏览：439

C语言训练-排序问题<2>-题解(C++代码)
浏览：184

你可能喜欢

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

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

　　作者: czy123　　　　发表时间：2020-03-30 13:42:12 浏览：904　|　评论：1　

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

```cpp
#include<iostream>
#include<cstring>
using namespace std;
/* dp[x][y][num][v+1]和dfs(int x,int y,int num,int v) dp数组用于存储防止重复计算 
不用 dp[x][y][num][v]存储因为v必须初始化-1，
如果初始化0，当宝物价值为0时，map[x][y]==v,无法拾取宝物，
当为v=-1数组无法存，只能向后错一位存；
建模：
dfs(int x,int y,int num,int v)
点(x,y)到点(n,m)还要再取num个宝物且宝物必须大于v的取法种数；
边界：当x==n,y==m;已经到最后一个宝物;
1.num==0不需要再去宝物 返回1；
2.num==1&&map[n][m]>v 还要再取一个且能取 返回1
用数组记录并返回dp[x][y][num][v+1]=1；
递归方程：
dfs(x,y,num,v) = 
当v<=map[x][y] 该宝物能取 
dfs(x+1,y,num+1,map[x][y])+dfs(x+1,y,num,v)+dfs(x,y+1,num+1,map[x][y])+dfs(x,y+1,num,v);
当v>map[x][y] 该宝物不能取
dfs(x+1,y,num,v)+dfs(x,y+1,num,v);  
总结：根据题目条件求(1,1)到(n,m)取k件宝物的总走法
只能往右下走所以肯定能从(1,2)到(n,m) (2,1)到(n,m)取k-1件or k件宝物的走法中获得;
因为不是随便取，必须取大于先前取得的宝物价值 所以要一个变量v记录所以4个变量
则建立dfs(x,y,num,v) 
dfs(1,1,k,-1)=........
*/
const int N=1000000007;
int n,m,k;
int map[51][51];
int dp[51][51][13][14];
int dfs(int x,int y,int num,int v){//num代表还要取num个宝物 
	if(dp[x][y][num][v+1]!=-1)return dp[x][y][num][v+1];//能在记忆数组中找到 
	int t=0;
	if(x==n&&y==m){//边界条件 
		if(num==0)t++;
		else if(map[x][y]>v&&num==1)t++;
	}
	if(x+1<=n){//能下走 
		if(map[x][y]>v)t+=dfs(x+1,y,num-1,map[x][y]);
		t%=N;
		t+=dfs(x+1,y,num,v);	
		t%=N;	 
	}
	if(y+1<=m){//能右走 
		if(map[x][y]>v)t+=dfs(x,y+1,num-1,map[x][y]);
		t%=N;
		t+=dfs(x,y+1,num,v);	
		t%=N;	 
	}
	return dp[x][y][num][v+1]=t;//把下右的结果相加 
}
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));
	cout << dfs(1,1,k,-1);
}
```

0.0分

9 人评分

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

　　评论区

杨鹏伟

解释的非常详细，比前面的几个讲解更加容易理解！！！！爱了爱了！！！！！！！！！！！！！！！！！！！！

2020-09-24 09:33:02

czy123

TA的其他文章

你可能喜欢

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

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

点我有惊喜！你懂得！

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

C语言训练-排序问题<1> （C语言代码）

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

评论区

精彩推荐

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

哥德巴赫曾猜测（C语言代码）

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

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

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

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

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

核桃的数量（C语言代码）

核桃的数量（C语言代码）

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

czy123

TA的其他文章

你可能喜欢

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

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

点我有惊喜！你懂得！

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

C语言训练-排序问题<1> （C语言代码）

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

评论区

精彩推荐

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

哥德巴赫曾猜测 （C语言代码）

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

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

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

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

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

核桃的数量 （C语言代码）

核桃的数量 （C语言代码）

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

　　评论区

哥德巴赫曾猜测（C语言代码）

核桃的数量（C语言代码）

核桃的数量（C语言代码）