Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-砍竹子
题目 2663:

蓝桥杯2022年第十三届省赛真题-砍竹子

时间限制: 1s 内存限制: 256MB 提交: 665 解决: 172

题目描述

这天,小明在砍竹子,他面前有 n 棵竹子排成一排,一开始第 i 棵竹子的高度为 hi .

他觉得一棵一棵砍太慢了,决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用,假设这一段竹子的高度为 H,那么使用一次魔法可以把这一段竹子的高度都变为蓝桥杯2022年第十三届省赛真题砍竹子,其中 ⌊x⌋ 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。 

输入格式

第一行为一个正整数 n,表示竹子的棵数。

第二行共 n 个空格分开的正整数 hi,表示每棵竹子的高度。 

输出格式

一个整数表示答案。 

样例输入

6
2 1 4 2 6 7

样例输出

5

提示

其中一种方案:

2 1 4 2 6 7

→ 2 1 4 2 6 2
→ 2 1 4 2 2 2
→ 2 1 1 2 2 2
→ 1 1 1 2 2 2
→ 1 1 1 1 1 1
共需要 5 步完成。
对于 20% 的数据,保证 n ≤ 1000, hi ≤ 106
对于 100% 的数据,保证 n ≤ 2 × 105, hi ≤ 1018



标签