[蓝桥杯][2014年第五届真题]地宫取宝

[蓝桥杯][2014年第五届真题]地宫取宝

题目描述：

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入
输入一行3个整数，用空格分开：n m k (1< =n,m< =50, 1< =k< =12)

接下来有 n 行数据，每行有 m 个整数 Ci (0< =Ci< =12)代表这个格子上的宝物的价值
输出

要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

样例输入

2 3 2
1 2 3
2 1 5

样例输出

14

做法一：

对大数据明显超时，就是简单的深搜加判断.

代码

#include<iostream>
using namespace std;
int n,m,k;
int a[50][50];
long long ans=0;
const int MOD = 1000000007; 
//这个函数就是一层走“一步” 
void dfs(int x,int y,int max,int cont){ 
	int cut = a[x][y]; //记录一下当前位置金额 
	
	// 终止条件
	if(x==n||y==m||cont>k) return;
	
	if(x==n-1&&y==m-1){//已经到达最后一个格子 
		if(cont==k){ //没拿继续走 
			ans++;
			if(ans>MOD)
				ans%=MOD;
			dfs(x+1,y,max,cont);
			dfs(x,y+1,max,cont);
		}
		if(cont==k-1&&cut>max) //刚好差一个且可以拿
		{
			ans++;
			if(ans>MOD)
				ans%=MOD;
// 接下来其实就到出口了，也可以不加 
			dfs(x+1,y,cut,cont+1);
			dfs(x,y+1,cut,cont+1);
		} 
	} 
	if(cut>max){
	//拿了继续走 
		dfs(x+1,y,cut,cont+1);
		dfs(x,y+1,cut,cont+1);
	//或者大于但是没拿 	
		dfs(x+1,y,max,cont);
		dfs(x,y+1,max,cont);		
	}
	// 价值小于
	else{ 
		dfs(x+1,y,max,cont);
		dfs(x,y+1,max,cont);		
	} 
}
int main(){

	
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	dfs(0,0,-1,0);
	cout<<ans;
}

做法二：动态规划，用数值记录

就是无论你是从那个方向来到我们这一层的，我们每进入一层dfs（a,b,c,d ) 如果四个参数都一样，那么这一层到结果所产生的有用次数也一样。那么我们就可以提前记录，避免重复递归。

代码：

#include<iostream>
#include<cstring>

using namespace std;
int n,m,k;
int a[50][50];
long long cache[50][50][14][13]; 
const int MOD = 1000000007; 
//这个函数就是一层走“一步” 

long long dfs(int x,int y,int max,int cont){ 
	//判断这一步有没有先前记录过 
	if(cache[x][y][max+1][cont]!=-1) 
		return cache[x][y][max+1][cont];
	
	long long ans=0; // 走这一步是否算	
	int cut = a[x][y];  
	
	 
	if(x==n||y==m||cont>k) return 0;
	
	if(x==n-1&&y==m-1){//已经到达最后一个格子 
		if(cont==k||(cont==k-1&&cut>max)){ //没拿继续走 
			ans++;
			if(ans>MOD)
				ans%=MOD;		
		}
		return ans;
		} 
// -----递归部分	
	if(cut>max){
	//拿了继续走 
		ans+= dfs(x+1,y,cut,cont+1);
		ans+= dfs(x,y+1,cut,cont+1);	
	}
	// 价值小于，大于但是没拿 
	ans+= dfs(x+1,y,max,cont);
	ans+= dfs(x,y+1,max,cont);	
//----------------------------------递归部分结束
	
	//每进一层就又新的四种可能，那你总得把你四种可能算完后要的到的东西
	//记录或者返回吧即下面这样
	// 全局变量就记录，ans就返回 
	
	//这里其实是记录"每一个"刚进去后，递归四种完四种可能出来后这一层的cache 
	cache[x][y][max+1][cont] = ans % MOD;
	return ans%MOD;	
	
}
int main(){

	//cache[0][0][0][0] = -1;
	memset(cache,-1,sizeof(cache));
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	cout<<dfs(0,0,-1,0)<<endl;
	//cout<<cache[0][0][0][0];
	return 0; 
		
}

本文地址：https://blog.csdn.net/Hgg657046415/article/details/108181254