Array Shrinking
题意翻译
### 题目描述
给你一个长度为 $n(1 \le n \le 500)$ 的数组 $a$,每次你可以进行以下两步操作:
1. 找到 $i \in [1, n)$,使得 $a_i = a_{i + 1}$;
2. 将 **它们** 替换为 $a_i + 1$。
每轮操作之后,显然数组的长度会减小 $1$,问剩余数组长度的最小值。
### 输入格式
第一行包含一个整数 $n(1 \le n \le 500)$,表示数组的原长。
第二行包含 $n$ 个整数 $a_1, a_2, \cdots a_n (1 \le a_i \le 1000)$,表示原数组 $a$。
### 输出格式
共一行仅一个整数 $num$,表示进行许多轮操作之后,$a$ 剩余长度的最小值。
### 样例解释
第一组样例中,最优操作之一为 $\text{4 3 2 2 3} \to \text{4 3 3 3} \to \text{4 4 3} \to \text{5 3}$
第二组样例中,最优操作之一为 $\text{3 3 4 4 4 3 3} \to \text{4 4 4 4 3 3} \to \text{4 4 4 4 4} \to \text{5 4 4 4} \to \text{5 5 4} \to \text{6 4}$
对于第三和第四组样例,你并不能进行任何操作。
题目描述
You are given an array $ a_1, a_2, \dots, a_n $ . You can perform the following operation any number of times:
- Choose a pair of two neighboring equal elements $ a_i = a_{i + 1} $ (if there is at least one such pair).
- Replace them by one element with value $ a_i + 1 $ .
After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $ a $ you can get?
输入输出格式
输入格式
The first line contains the single integer $ n $ ( $ 1 \le n \le 500 $ ) — the initial length of the array $ a $ .
The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 1000 $ ) — the initial array $ a $ .
输出格式
Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.
输入输出样例
输入样例 #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
说明
In the first test, this is one of the optimal sequences of operations: $ 4 $ $ 3 $ $ 2 $ $ 2 $ $ 3 $ $ \rightarrow $ $ 4 $ $ 3 $ $ 3 $ $ 3 $ $ \rightarrow $ $ 4 $ $ 4 $ $ 3 $ $ \rightarrow $ $ 5 $ $ 3 $ .
In the second test, this is one of the optimal sequences of operations: $ 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 $ .
In the third and fourth tests, you can't perform the operation at all.