合并塔楼(Towers)

题目描述

城市 D 由 $n$ 个塔楼组成，这些塔楼依次沿一条直线建造。从左到右，第 $i$ 个塔楼的高度为 $h_i$。市长决定重建城市，使其变得更加美丽。在一个美丽的城市中，所有的塔楼从左到右高度应满足非递减顺序。

重建操作包括进行若干次（可能为零次）操作。每次操作可以用起重机将任意一个塔楼整体移动到相邻的某个塔楼上方，也就是说，我们可以把第 $i$ 个塔楼放到第 $(i-1)$ 个塔楼（如果存在）或者第 $(i+1)$ 个塔楼（如果存在）的上面。合并之后，新塔楼的高度等于被合并的两个塔楼高度之和。被合并的塔楼在之后不能再分开，但可以继续进行类似合并操作。注意每次合并后，塔楼总数减少 $1$ 个。

请帮助市长确定使城市变得美丽所需的最少操作次数。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 5000$），表示城市中的塔楼数量。
第二行包含 $n$ 个以空格分隔的整数 $h_i$（$1 \le h_i \le 10^5$），表示从左到右初始序列中第 $i$ 个塔楼的高度。

输出格式

输出一个整数，表示使城市变得美丽所需的最少操作次数。

样例输入 #1

5
8 2 7 3 1

样例输出 #1

3

样例输入 #2

3
5 2 1

样例输出 #2

2

数据范围

由 ChatGPT 5 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接