[蓝桥杯][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
上一篇: js中过滤特殊字符的正则表达式