kuai

用户名：kuai

访问量：5099

签　名：

等　　级
排　　名	4788
经　　验	1637
参赛次数	0
文章发表	10
年　　龄	0
在职情况	学生
学　　校	黄龙山职院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-夺宝奇兵-题解(C++代码)
浏览：590

蓝桥杯算法提高VIP-开灯游戏-题解-DFS模板题(C++代码)
浏览：479

蓝桥杯算法提高VIP-彩票-find()函数
浏览：274

你可能喜欢

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

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

优质题解

蓝桥杯算法提高VIP-夺宝奇兵-题解(C++代码)

　　作者: kuai　　　　发表时间：2020-04-15 17:42:34 浏览：590　|　评论：2　

原题链接：蓝桥杯算法提高VIP-夺宝奇兵

```cpp
/*

题目描述
在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:

7
3  8
8  1  0
2  7  4  4
4  5  2  6  5

”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5-> 7-> 8-> 3-> 7的顺序,将得到最大值30
输入
第一行正整数N(100> =N> 1),表示山的高度 
接下来有N行非负整数,第i行有i个整数(1< =i< =N),表示山的第i层上从左到右每条路上的珠宝数目 
输出
一个整数,表示从山底到山顶的所能得到的珠宝的最大数目. 
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30

/*
重点：
	1、只能向左、向上走一步

从下向上值最大，和从上向下值最大，路径是一样的 
最优子结构十分明显，从最高层出发，每一次走 值最大 的那条路径

设 num[i][j] 保存该位置上的价值 
	设 dp[i][j] 表示从 (i,j) 走到最底层的最大价值
	状态转移：
		dp[i][j] = num[i][j] + max(dp[i+1][j],dp[i+1][j+1])

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;
int num[102][102];			//存放原始地图 
int dp[102][102];			// dp 数组 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int res = 0;
	int n;	
	cin>>n;
	for(int i = 1;i <= n;++i)
		for(int j  = 1;j <= i;++j)
			cin>>num[i][j];
			
	// 对 dp 数组边界初始化		
	for(int i = 1;i <= n;++i)
		dp[n][i] = num[n][i];
		
	for(int i = n-1;i >= 1;i--)
		for(int j = 1;j <= i;j++)
			dp[i][j] = num[i][j] + max(dp[i+1][j],dp[i+1][j+1]);
			
	cout<<dp[1][1];
	
	return 0;
}

/*
int n;				//山的高度
int num[102][102];	// 保存价值
int dp[102][102]; 
int main(){
	cin>>n;
	for(int i = 0;i < n;++i)
		for(int j = 0;j <= i;++j){
			cin>>num[i][j];
		}
	for(int i = 0;i < n;++i)
		
	
	
	return 0;
}*/
```

0.0分

1 人评分

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

　　评论区

早起床

这个题的思路很简单。但是需要自己找题目的条件，这才是难点

2022-10-13 13:47:00

为什么只能向上和向左？

2020-04-25 15:26:31

kuai

TA的其他文章

你可能喜欢

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

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

C二级辅导-公约公倍（C语言代码）

弟弟的作业（C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

蓝桥杯算法提高VIP-夺宝奇兵-题解(C++代码)

评论区

精彩推荐

不容易系列（C语言代码）

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

C语言考试练习题_一元二次方程（C语言代码）

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

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

简单的a+b （C语言代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

图形输出（C语言代码）

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

kuai

TA的其他文章

你可能喜欢

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

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

C二级辅导-公约公倍 （C语言代码）

弟弟的作业 （C++代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

蓝桥杯算法提高VIP-夺宝奇兵-题解(C++代码)

评论区

精彩推荐

不容易系列 （C语言代码）

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

C语言考试练习题_一元二次方程 （C语言代码）

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

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

简单的a+b （C语言代码）

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

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

图形输出 （C语言代码）

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

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

C二级辅导-公约公倍（C语言代码）

弟弟的作业（C++代码）

　　评论区

不容易系列（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

图形输出（C语言代码）