P10622 [ICPC 2013 WF] Matryoshka


套娃是俄罗斯传统木制玩具，由一组逐渐变小的娃娃组成，依次放置在另一个娃娃内部。一个套娃可以打开，露出一个更小的类似玩偶，而这个玩偶内部又有另一个玩偶，以此类推。 俄罗斯套娃博物馆最近展出了一系列设计相似的套娃，不同之处仅在于每套娃娃中嵌套的数量不同。不幸的是，一些过于热心（显然没有得到监督）的孩子把这些套娃拆散了，并将所有的单个娃娃排成一行。现在这一行中有 $n$ 个娃娃，每个都有一个整数大小。你需要重新组装这些套娃，既不知道套娃的数量，也不知道每套娃娃中娃娃的数量。你只知道每套完整的套娃由大小从 $1$ 到某个数字 $m$ 的连续大小的娃娃组成，而这个数字 $m$ 在不同的套娃中可能有所不同。 在重新组装套娃时，你必须遵循以下规则： - 你只能将一个娃娃或一个嵌套的娃娃组放入一个更大的娃娃中。 - 你只能合并两个在行中相邻的娃娃组。 - 一旦一个娃娃成为一个组的成员，它不能被转移到另一个组或永久地从组中分离。它只能在合并两个组时暂时分离。 你的时间非常宝贵，你希望尽快完成这个重新组装过程。这个任务中唯一耗时的部分是打开和随后关闭一个娃娃，因此你希望尽量减少这样的操作次数。例如，当将组 $[1, 2, 6]$ 与组 $[4]$ 合并时，最少需要进行两次开关操作，因为你必须打开大小为 $6$ 和 $4$ 的娃娃。而当将组 $[1, 2, 5]$ 与组 $[3, 4]$ 合并时，需要进行三次开关操作。 编写一个程序计算重新组装所有拆散的套娃所需的最少开关次数。

无

无