luogu#P7641. [BalticOI 2006 Day 2] RLE COMPRESSION
[BalticOI 2006 Day 2] RLE COMPRESSION
题目描述
RLE 是一种简单的压缩算法,用于压缩包含相同字符后续重复的序列。 通过压缩特定的序列,我们获得其编码。这个想法是用一个计数器表示给定字符(例如 )的重复,以表示有多少次重复。即,我们用包含重复标记,重复字符和代表重复次数的整数的三元组来表示它。 例如, 可以编码为 (其中 表示重复标记)。
我们需要以某种方式表示字母,重复标记和计数器。让字母由 个字符组成,这些字符由集合 中的整数表示。来自 的字符序列的编码也是来自 的字符序列。 在任何时候,重复标记都由 中的字符表示,用 表示。最初 为 ,但在编码过程中可能会改变。
该编码解释如下:
- 除重复标记外,编码中的任何字符 都表示自身;
- 如果编码中出现重复标记 ,则以下两个字符具有特殊含义:
如果 后面跟着 ,则表示 的 个重复,
否则,如果 后跟 (其中 ),则 将是从该点开始的重复标记,
否则,如果 后面跟随 (其中 并且 ),则它表示 的 个重复。
使用上述方案,我们可以从 编码任何字符序列。例如,对于 ,序列 可以编码为 。编码 的第一个字符表示简单 。接下来的 编码为 。然后, 表示 , 表示 ,而 将重复标记切换为 ,然后 代表自己,最后 编码 。
序列可以以多种方式编码,并且编码长度可以变化。给定一个已经编码的序列,您的任务是查找字符数最少的编码。
编写一个程序,该程序:
- 读取字母的大小和序列的编码。
- 查找该序列的最短编码。
- 写出结果。
输入格式
第一行包含一个整数 :字母的大小。第二行包含一个整数 :编码的长度。最后一行包含 中的 个整数,这些整数之间用单个空格分隔,表示序列的编码。
输出格式
第一行应包含一个整数 :代表给定序列的编码中最少的字符数。输出的最后一行应包含集合 中的 个整数,以单个空格分隔:该序列的编码。如果存在几个最短的序列,则程序应输出其中的任何一个。
4
20
1 0 0 1 0 2 3 0 3 2 0 1 0 0 3 0 2 1 0 1
19
1 0 1 0 0 0 1 2 3 1 3 2 0 3 0 2 1 0 1
14
15
10 10 10 0 10 0 10 10 13 10 10 13 10 10 13
9
0 10 13 0 10 13 0 10 10
提示
数据规模与约定
对于 的数据,,。
题目说明
来源于 Baltic Olympiad in Informatics 2006 的 Day 2:RLE。
由
/user/274209