欧名意

用户名：uq_42083064726

访问量：2270

签　名：

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

　　自我简介：

TA的其他文章

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

蓝桥杯算法提高VIP-最长单词-题解(C++代码)
浏览：605

你可能喜欢

蓝桥杯算法提高-秘密行动-题解(C++代码)

　　作者: 欧名意　　　　发表时间：2020-03-01 13:40:49 浏览：792　|　评论：0　

原题链接：蓝桥杯算法提高-秘密行动

题目描述：

小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。

输入：

第一行包含一个整数n，代表楼的高度。
接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。

输出：

输出1行，包含一个整数，表示所需的最短时间。

样例输入：
5
3
5
1
8
4

样例输出：
1

解题思路：深度优先搜索，动态规划
1.深度优先搜索，在我看到题目的时候我就想用dfs但是呢，因为数据量太大，最后会导致运行超时，这样可划不来，而且这道题目也不好剪枝，也不能剪多少，所以不推荐用dfs来写。
2.我参考了网上其他博主写的，我觉得都挺好的，有2种写法，但是我觉得换汤不换药，本质是一样一样的（我未经允许复制的链接，若是不喜，联系我删）

（1）https://blog.csdn.net/tgj2094942564/article/details/104542241
这位博主，我觉得写得很详细，很容易懂，他写的内容我就不在重复。我在他写的代码的基础上在优化了一下，少了一个数组，输入和计算放在了一个循环里面。我的代码如下：
```cpp
#include<iostream>
using namespace std;
int jump[10005];
int climb[10005];
int m_min(int x,int y)
{
	return x<y?x:y;
}
int  main()
{
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>climb[i];
		if(i>1)jump[i]=m_min(climb[i-1],climb[i-2]);
		climb[i]=m_min(climb[i-1],jump[i-1])+climb[i];
	}
	int ans=m_min(jump[n],climb[n]);
	cout<<ans<<endl;
	return 0;
}
```

（2）https://blog.csdn.net/liulizhi1996/article/details/104320687?depth_1-utm_source=distribute.pc_relevant_right.none-task&utm_source=distribute.pc_relevant_right.none-task
如果看懂了第一种写法，那么这一种应该很容易理解，只是把2个数组并到了一个二维数组里面。我写的代码也和上面那个差不多，代码如下：
```cpp
#include<iostream>
using namespace std;
int step[10005][2];
int m_min(int x,int y)
{
	return x<y?x:y;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>step[i][0];
		if(i>1) step[i][1]=m_min(step[i-1][0],step[i-2][0]);
		step[i][0]=m_min(step[i-1][0],step[i-1][1])+step[i][0];
	}
	int ans=m_min(step[n][0],step[n][1]);
	cout<<ans<<endl;
	return 0;
}
```

谢谢参考！

0.0分

3 人评分

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

欧名意

TA的其他文章

你可能喜欢

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

Hello, world! （C语言代码）

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

矩形面积交（C语言代码）

汽水瓶（C语言代码）

蓝桥杯算法提高-秘密行动-题解(C++代码)

评论区

精彩推荐

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

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

兰顿蚂蚁（C++代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

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

哥德巴赫曾猜测（C语言代码）

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

C语言训练-亲密数（C语言代码）

1908题解

有关字符，字符串的输入输出函数说明

欧名意

TA的其他文章

你可能喜欢

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

Hello, world! （C语言代码）

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

矩形面积交 （C语言代码）

汽水瓶 （C语言代码）

蓝桥杯算法提高-秘密行动-题解(C++代码)

评论区

精彩推荐

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

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

兰顿蚂蚁 （C++代码）

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

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

哥德巴赫曾猜测 （C语言代码）

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

C语言训练-亲密数 （C语言代码）

1908题解

有关字符，字符串的输入输出函数说明

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

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

矩形面积交（C语言代码）

汽水瓶（C语言代码）

　　评论区

兰顿蚂蚁（C++代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

哥德巴赫曾猜测（C语言代码）

C语言训练-亲密数（C语言代码）