用户

用户名：18375791271

访问量：5496

签　名：

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

　　自我简介：

TA的其他文章

K-进制数-题解(C++代码)
浏览：143

蓝桥杯2014年第五届真题-地宫取宝-题解记忆化搜索法
浏览：217

你可能喜欢

蓝桥杯2014年第五届真题-地宫取宝-题解记忆化搜索法

　　作者: 用户　　　　发表时间：2019-11-20 21:39:00 浏览：217　|　评论：1　

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

#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const ll INF = 1000000007;
    ll mp[55][55][15][15];//记录搜索时状态
    int edge[55][55];//记录图
    int n,m,k;
    int dist[2][2]={1,0,0,1};//位移
    ll dfs(int x,int y,int key,int mm){
    	if(x>n||y>m||key>k)	return 0;
    	if(mp[x][y][key][mm]!=-1) return mp[x][y][key][mm];//记忆化如果以前处理过直接查表拿值
    	if(x==n&&y==m){
    		if(key==k||(key==k-1&&mm<edge[n][m])){//当到达终点拿到的数量为k或者为k-1但是终点大于最大值时，返回结果。
    			return 1;
    		}		
    	}
    	ll s=0;
    	for(int i=0;i<2;i++){
    		int xx = x+dist[i][0];
    		int yy = y+dist[i][1];
    		if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
    			if(edge[x][y]>mm){//当前值大于目前最大值，可以拿上
    				s+=dfs(xx,yy,key+1,edge[x][y])%INF;
    			}	
    			s+=dfs(xx,yy,key,mm)%INF;//不拿当前值
    			s%INF;
    		}
    	}
    	return mp[x][y][key][mm]=s%INF;
    	
    }
    void init(){
    	memset(mp,-1,sizeof(mp));
    }
    int main(){
    	//freopen("e:/in.txt","r",stdin);
    	cin>>n>>m>>k;
    	init();
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>edge[i][j];
    			edge[i][j]++;//因为价值可以为0，那么传值时要比0小就为负值，数组会报错，所以所有价值加1
    		}
    	}
    	cout<<dfs(1,1,0,0)%INF;
    }

0.0分

0 人评分

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

　　评论区

╰*★.oоО

不要乱来！

2020-10-02 21:38:33

用户

TA的其他文章

你可能喜欢

C二级辅导-统计字符（C语言代码）

采药（C++代码）

C二级辅导-求偶数和（C语言代码）

C语言训练-阶乘和数* （C语言代码）

C二级辅导-同因查找（C语言代码）

蓝桥杯2014年第五届真题-地宫取宝-题解记忆化搜索法

评论区

精彩推荐

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

最小公倍数（C语言代码）

用筛法求之N内的素数。（C语言代码）

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

printf基础练习2 （C语言代码）

字符串的输入输出处理（C语言代码）

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

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

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

用户

TA的其他文章

你可能喜欢

C二级辅导-统计字符 （C语言代码）

采药 （C++代码）

C二级辅导-求偶数和 （C语言代码）

C语言训练-阶乘和数* （C语言代码）

C二级辅导-同因查找 （C语言代码）

蓝桥杯2014年第五届真题-地宫取宝-题解记忆化搜索法

评论区

精彩推荐

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

最小公倍数 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

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

printf基础练习2 （C语言代码）

字符串的输入输出处理 （C语言代码）

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

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

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

C二级辅导-统计字符（C语言代码）

采药（C++代码）

C二级辅导-求偶数和（C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

最小公倍数（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符串的输入输出处理（C语言代码）