luogu#P7641. [BalticOI 2006 Day 2] RLE COMPRESSION

[BalticOI 2006 Day 2] RLE COMPRESSION

题目描述

RLE 是一种简单的压缩算法,用于压缩包含相同字符后续重复的序列。 通过压缩特定的序列,我们获得其编码。这个想法是用一个计数器表示给定字符(例如 aaaaa\texttt{aaaaa})的重复,以表示有多少次重复。即,我们用包含重复标记,重复字符和代表重复次数的整数的三元组来表示它。 例如,aaaaa\texttt{aaaaa} 可以编码为 #a5\texttt{#a5} (其中 \texttt{#} 表示重复标记)。
我们需要以某种方式表示字母,重复标记和计数器。让字母由 nn 个字符组成,这些字符由集合 Σ={0,1,,n1}\Sigma= \lbrace 0,1, \cdots ,n-1 \rbrace 中的整数表示。来自 Σ\Sigma 的字符序列的编码也是来自 Σ\Sigma 的字符序列。 在任何时候,重复标记都由 Σ\Sigma 中的字符表示,用 ee 表示。最初 ee00,但在编码过程中可能会改变。
该编码解释如下:

  • 除重复标记外,编码中的任何字符 aa 都表示自身;
  • 如果编码中出现重复标记 ee,则以下两个字符具有特殊含义:
    \circ 如果 ee 后面跟着 ekek,则表示 eek+1k+1 个重复,
    \circ 否则,如果 ee 后跟 b0b0(其中 b=/eb {=}\mathllap{/\,} e),则 bb 将是从该点开始的重复标记,
    \circ 否则,如果 ee 后面跟随 bkbk(其中 b=/eb {=}\mathllap{/\,} e 并且 k>0k>0),则它表示 bbk+3k+3 个重复。

使用上述方案,我们可以从 Σ\Sigma 编码任何字符序列。例如,对于 n=4n=4,序列 1002222223333303020000\texttt{1002222223333303020000} 可以编码为 10010230320100302101\texttt{10010230320100302101}。编码 1\texttt{1} 的第一个字符表示简单 1\texttt{1}。接下来的 001\texttt{001} 编码为 00\texttt{00}。然后,023\texttt{023} 表示 222222\texttt{222222}032\texttt{032} 表示 33333\texttt{33333},而 010\texttt{010} 将重复标记切换为 1\texttt{1},然后 0302\texttt{0302} 代表自己,最后 101\texttt{101} 编码 0000\texttt{0000}
序列可以以多种方式编码,并且编码长度可以变化。给定一个已经编码的序列,您的任务是查找字符数最少的编码。
编写一个程序,该程序:

  • 读取字母的大小和序列的编码。
  • 查找该序列的最短编码。
  • 写出结果。

输入格式

第一行包含一个整数 nn:字母的大小。第二行包含一个整数 mm:编码的长度。最后一行包含 {0,1,,n1}\lbrace 0,1, \cdots ,n−1 \rbrace 中的 mm 个整数,这些整数之间用单个空格分隔,表示序列的编码。

输出格式

第一行应包含一个整数 mm':代表给定序列的编码中最少的字符数。输出的最后一行应包含集合 {0,1,,n1}\lbrace 0,1, \cdots ,n−1 \rbrace 中的 mm' 个整数,以单个空格分隔:该序列的编码。如果存在几个最短的序列,则程序应输出其中的任何一个。

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

提示

数据规模与约定

对于 100%100 \% 的数据,2n1052 \le n \le 10^51m2×1061 \le m \le 2×10^6

题目说明

来源于 Baltic Olympiad in Informatics 2006Day 2:RLE

/user/274209