Responsive image

问题 2564 --第十三届蓝桥杯-试题 J: 砍竹子

2564: 第十三届蓝桥杯-试题 J: 砍竹子

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的 高度为 hi . 他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以 把这一段竹子的高度都变为      ⌊ √ ⌊ H 2 ⌋ + 1⌋，其中 ⌊x⌋ 表示对 x 向下取整。小明想 知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。 

输入描述

第一行为一个正整数 n，表示竹子的棵数。 第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
对于 20% 的数据，保证 n ≤ 1000, hi ≤ 1e6。
 对于 100% 的数据，保证 n ≤ 2 × 1e5 , hi ≤ 1e18。

输出描述

一个整数表示答案。

样例输入

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 步完成

来源

第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组-20李硕硕 

[提交][状态]
ACM算法攻关部