欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-22 14:46:35
[蓝桥杯][2014年第五届真题]地宫取宝题目描述:X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角,出口在右下角。小明被带到地宫的入口,国王要求他只能向右或向下行走。走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。...

[蓝桥杯][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

相关标签: 备战蓝桥杯