kuai

用户名：kuai

访问量：4723

签　名：

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

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-我们的征途是星辰大海-模拟+读题
浏览：242

蓝桥杯算法提高VIP-打水问题 -贪心
浏览：295

蓝桥杯算法提高VIP-排队打水问题-贪心（对比 1520打水问题）
浏览：749

你可能喜欢

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

　　作者: kuai　　　　发表时间：2020-04-15 17:42:34 浏览：555　|　评论：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的其他文章

你可能喜欢

Hello, world! （Java代码）

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

C二级辅导-温度转换（C语言代码）

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

人民币问题（C语言代码）

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

评论区

精彩推荐

C语言考试练习题_保留字母（C语言代码）

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

C二级辅导-等差数列（C语言代码）

破解简单密码（C语言代码）

程序员的表白（C语言代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

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

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

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

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

kuai

TA的其他文章

你可能喜欢

Hello, world! （Java代码）

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

C二级辅导-温度转换 （C语言代码）

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

人民币问题 （C语言代码）

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

评论区

精彩推荐

C语言考试练习题_保留字母 （C语言代码）

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

C二级辅导-等差数列 （C语言代码）

破解简单密码 （C语言代码）

程序员的表白 （C语言代码）

C语言训练-计算一个整数N的阶乘 （C语言代码）

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

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

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

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

C二级辅导-温度转换（C语言代码）

人民币问题（C语言代码）

　　评论区

C语言考试练习题_保留字母（C语言代码）

C二级辅导-等差数列（C语言代码）

破解简单密码（C语言代码）

程序员的表白（C语言代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

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