图片压缩

百万种颜色,栩栩如生J。然而,高分辨率的图片往往需要很大的存储空间L。为此,小明正在研究一种简单的图片压缩技术: ●对象:用来压缩16色的图片(每个象素的颜色用0到15表示); ●方式: 压缩后的编码用一个一个8位的字节来表示的:前4位为颜色,后4位为该颜色此后连续出现多少次。例如,一张图片压缩后的编码为:0010001100010100。第一个字节表示:代号为(0010)2=2的颜色连续出现(0011)2=3次;随后,代号为(0001)2=1的颜色连续出现了(0100)2= 4次。这样,就知道还原压缩后,图片有7个颜色象素依次为:2221111。●效果: 如果不改变原图片的颜色,则1121压缩后需要用3个字节来存储:0001001000100001 00010001,压缩效果不好。而若将其中的2改变成1,则只需要用1个字节来存储:00010100。当然,代价是图片有所失真。设原先图片颜色描述为数列A,压缩后还原的图片颜色描述为数列B,则失真指数=∑│Ai-Bi│压缩指数=压缩后存储需要的字节数×2 总体效果值=失真指数+压缩指数例如:1121用000100100010000100010001来压缩,其失真指数为0,压缩指数为6,总体效果值为6;如果用00010100来压缩,其失真指数为1,压缩指数为2,总体效果值为3。总体效果值越低,表示压缩的越好。为了验证自己压缩算法的优良性,小明希望你能编写一个程序,帮助他以最低的总体效果值来压缩一幅图片。输入文件:piczip.in 输入文件第一行有一个数N,表示原图片的颜色象素数。(1≤ N≤ 5000) 第二行有N个在[0,15]内的整数,依次表示原图中每个象素的颜色。输出文件:piczip.out 输出文件有一行,一个整数表示压缩后最低的总体效果值。样例输入:piczip.in 4 1121 样例输出:piczip.out 3