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。

编码所需要的最少位数。

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

动规专题