← 返回题目列表

Codeforces · 1312/E

E. 数组缩小

中文机器翻译题面 查看原题

给你一个数组 $$$a_1, a_2, \dots, a_n$$$。您可以多次执行以下操作:

- 选择一对两个相邻的相等元素 $$$a_i = a_{i + 1}$$$ (如果至少有一个这样的对)。
- 将它们替换为值为 $$$a_i + 1$$$ 的一个元素。

每次这样的操作之后,数组的长度将减少一(并且元素会相应地重新枚举)。您可以获得的数组 $$$a$$$ 的最小可能长度是多少?

输入

第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 数组 $$$a$$$ 的初始长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — 初始数组 $$$a$$$。

输出

打印唯一的整数——执行上述操作任意次数后可以获得的最小可能长度。

示例

输入 #1

5
4 3 2 2 3

输出 #1

2

输入 #2

7
3 3 4 4 4 3 3

输出 #2

2

输入 #3

3
1 3 5

输出 #3

3

输入#4

1
1000

输出#4

1

注意

在第一个测试中,这是最佳操作顺序之一: $$$4$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$\rightarrow$$$ $$$5$$$ $$$3$$$。

在第二个测试中,这是最佳操作顺序之一: $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$5$$$ $$$4$$$$$$\rightarrow$$$$$$6$$$$$$4$$$。

在第三次和第四次测试中,您根本无法执行该操作。