3029 - 图像压缩

图像的数字表达是由r行s列的数字所组成的二维矩阵(二维数组)。矩阵(数组)中每个值的取值范围为[0,255]。>图像的数字表达是由r行s列的数字所组成的二维矩阵(二维数组)。矩阵(数组)中每个值的取值范围为[0,255]。

图像压缩需要将所有数据排成一行,比如将第2行接在第1行之后,第i+1行接到第i行之后,得到数字序列p1,p2,...,pn。用二进制数来表示pi,得到图像编码。因为pi取值范围为[0,255],所以可以用8位二进制来表示pi,比如0000011001011011表示第一数字为6,第二个数字为91.

如果每个数字都用8位来表示的话,太浪费空间了。比如240,190,255,130,5,4,7,6,3,5这十个数,如果每个数字都用8位来表示的话,需要80位存储空间。如果将前4个作为一组用8位来表示,后6个为一组用3位来表示,同时在每一组的开头加上这一组所用的位数(第一组为8)和长度(第一组为4),则可以节省空间。假定长度不超过255(即需要8位表示长度),位数不超过8(8只需要3位表示),所以每一组的开头需要加上11位。在本例中,存储空间为11+4*8+11+6*3=72位,显然比80位节约空间。

可以看出,图像压缩的核心问题是如何给数据分段。

输入

第一行为一个数n。 第二行为n个数,分别为p1,…,pn。

输出

编码所需要的最少位数。

样例

输入

10
240 190 255 130 5 4 7 6 3 5

输出

72

提示

对100%的数据,n≤10^6.

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题