蓝桥杯 2022 省 B 洛谷 P8787 砍竹子
[蓝桥杯 2022 省 B] 砍竹子
题目描述
这天，小明在砍竹子，他面前有 n n n 棵竹子排成一排，一开始第 i i i 棵竹子的高度为 h i h_{i} hi.
他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H H H，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊ ⌊ H 2 ⌋ + 1 ⌋ \left\lfloor\sqrt{\left\lfloor\frac{H}{2}\right\rfloor+1}\right\rfloor ⌊⌊2H⌋+1⌋, 其中 ⌊ x ⌋ \lfloor x\rfloor ⌊x⌋ 表示对 x x x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1 1 1。
输入格式
第一行为一个正整数 n n n，表示竹子的棵数。
第二行共 n n n 个空格分开的正整数 h i h_{i}