每日一题--小Q爬塔

发表于 | 分类于 |

题目描述：

小Q 正在攀登一座宝塔，这些宝塔很特别。塔总共有 n 层，但是每两层之间的净高却不相同，所以造成了小Q 爬过每层的时间也不同。如果某一层的高度为 x，那么爬过这一层所需的时间也是 x。小Q 还会使用一种魔法，每用一次就可以让他向上跳一层或两层，但是每次跳跃后小 Q 都将用完魔法力，必须爬过至少一层才能再次跳跃（你可以认为小 Q 需要跳两次一层才休息，最后也可以跳到塔外即超过塔高，挑是不消耗时间的）。

小 Q 享用最短的时间爬过塔顶，希望你能告诉他最短时间是多少？

输入描述：

第一行一个数 $n (n \leq 10000)$，表示塔的层数。

接下来的 n 行每行一个数 $h (1 \leq h \leq 100)$，表示从下往上每层的高度

输出描述：

一个数，表示最短时间

样例：

输入：

1
2
3
4
5
6
5
3
5
1
8
4

输出：

1
1

思路：

一开始想的是跟爬楼梯一样，就是一个改进版，后来发现爬楼梯将登上第 i 层的状态分为了第 i - 1 层和第 i - 2 层，所以才有 $f(i) = min(f(i - 1), f(i - 2))$ 的转移方程，但是这个方程式对于这一道题其实是不适用的。因为对于第 i 层可以由第 i - 1 层和第 i - 2 层转化过来的，但是第 i - 1 层到第 i 层有 ‘爬’ 和 ‘跳’ 两种方式，所以这个转移方程式就不适用了。

那么我们怎么来更改这个转移方程是呢？

因为第 i - 1 层有两种方式，这里我们就用 climb 和 jump 两个数组来分别表示两种方式：

jump[i] 表示 ‘爬’ 到第 i 层的最短时间

climb[i] 表示 ‘跳’ 到第 i 层的最短时间

这里就分为两种情况：

  • 到达第 i 层方法是爬：

第 i - 1 层有两种情况，可以是爬，也可以是跳，情况如下：

climb[i] = min(climb[i - 1], jump[i - 1]) + a[i]

  • 到达第 i 层是跳：

那么可以从第 i - 1 层跳，也可以从第 i - 2 层跳，那么：

climb[i] = min(jump[i - 1], jump[i - 2])

最后在 climb[n] 和 jump[n] 中取最小值即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int jump[10005], climb[10005];
int main() {
	int n, m, x;
	cin >> n;
	for(int i = 1; i <= n; ++i) {
        cin >> x;
        climb[i] = min(climb[i - 1], jump[i - 1]) + x;
        if(i == 1) continue;
        jump[i] = min(climb[i - 1], climb[i - 2]);
	}
	cout << min(climb[n], jump[n]) << endl;
    return 0;
}