第 1 题 鹅卵石 (pebbles)

时间限制 1.0 s · 空间限制 256 MB · 152 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 pebbles.in，输出文件 pebbles.out。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在一排左右排列的 $N$ 个地点中，每个地点上都放有若干个鹅卵石。

哲洙可以进行的操作有以下两种：

1. 从相邻的两个地点中，拿走任意相同数量的鹅卵石；
2. 从一个地点中，拿走任意数量的鹅卵石。

即使某个地点上的鹅卵石被拿完，该地点依旧保留，两个原本不相邻的地点不会因此变得相邻。

哲洙会不断重复执行上述两种操作中的一种，直到将所有鹅卵石都拿走。

给定每个地点初始时的鹅卵石数量，请编写一个程序，计算哲洙最少需要多少次操作，才能拿走所有鹅卵石。

输入格式

第一行给出地点数量 $N$。

第二行给出 $N$ 个整数，表示每个地点的初始鹅卵石数量，按从左至右的顺序，以空格分隔。

输出格式

输出一行，表示拿走所有鹅卵石所需的最少操作次数。

样例

样例 1

输入：

2
1 2

输出：

2

样例 2

输入：

4
1 1 3 3

输出：

2

样例 3

输入：

3
1 4 3

输出：

2

样例 4

输入：

5
2 3 6 10 5

输出：

4

提示

约束条件

• $2 \le N \le 2500$
• 每个地点初始的鹅卵石数量为不小于 1 且不超过 $10^5$ 的整数

子任务

1. （6 分）$N = 3$
2. （11 分）$N \le 15$
3. （19 分）$N \le 300$
4. （27 分）每个地点的初始鹅卵石数量不超过 2500
5. （37 分）无额外约束条件

翻译由 ChatGPT-4o 完成