logo AlgoBeat OnlineJudge
登录 注册

#101352. [BZOJ 1352] [Baltic2006]RLE COMPRESSION

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: 匿名

题目描述

有一种很简单的压缩方式,用于表示连续的若干个相同的字符。

例如 aaaaa 可以压缩成 #a5。其中 # 表示下面的部分是压缩的,a 是重复字符, 是重复次数。

在这个问题里,字符集也用整数代替,从

# 也用 中的一个数表示,初始时都用 表示,但是可以变;

重复次数也在 之间。也就是说原先的一个数列压缩以后,还是由 范围内的数构成的数列。

压缩的规定如下:

  1. 除了 # 以外的所有数,都表示原本的字符。

  2. 如果当前 # 用数 表示, 如果出现了,那么:

  • 如果后面紧跟 e k ,那么说明编号为 的字符重复
  • 如果后面紧跟 b 0 不是 ,说明从这里往后 # 用数 来表示
  • 如果后面紧跟 b k 不是 ,则表示编号为 的字符重复

例如当 时,原本的序列是 1002222223333303020000,经过压缩后的一种表示方式是 10010230320100302101

给出一个压缩后的数列,求原数列的哪个压缩数列长度最小,并输出该压缩数列。

输入格式

第一行是

第二行是 ,表示压缩数列的长度。

接下来的一行中有 个整数,都在 之间,表示一个压缩数列

输出格式

第一行输出同样表示原数列的最短压缩数列的长度。

样例

样例输入 #1

4
20
1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1

样例输出 #1

19

样例输入 #2

14
15
10 10 10 0 10 0 10 10 13 10 10 13 10 10 13

样例输出 #2

9

数据范围与提示

对于 的数据,满足