[ 算法 ] 图像压缩

问题

图像的数字表达是由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+48+11+63=72位，显然比80位节约空间。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
using namespace std;

long long length(int i);
void Compress(int n, int p[], int s[], int l[], int b[]);
//void Tracebace(int n, int& i, int s[], int l[]);
int a = 0;

void Compress(int n, int p[], int s[], int l[], int b[])
{
    int Lmax = 255, header = 11;
    s[0] = 0;

    //将存入的数字逐一取出
    for (int i = 1; i <= n; i++)
    {

        b[i] = length(p[i]);//当前数的位数
        int bmax = b[i];

        s[i] = s[i - 1] + bmax;//记录
        l[i] = 1;

        for (int j = 2; j <= i && j <= Lmax; j++)
        {
            //筛选出最大长度(即与上一次状态的数值的长度比较)
            if (bmax < b[i - j + 1])
            {
                bmax = b[i - j + 1];
            }

            //开始累加数 当位数不足时也按照最大长度来表示
            if (s[i] > s[i - j] + j * bmax)
            {
                s[i] = s[i - j] + j * bmax;
                l[i] = j;//记录当前状态位数最大值位置(即分段位置)
            }
        }
        s[i] += header;
    }
}

//转二进制数长度
long long length(int i)
{
    int k = 1;
    i = i / 2;
    while (i > 0)
    {
        k++;
        i = i / 2;
    }
    return k;
}

//void Traceback(int n, int& i, int s[], int l[])
//{
//    if (n == 0)
//        return;
//    Traceback(n - l[n], i, s, l);
//    s[i++] = n - l[n];
//}

int main()
{
    int n;
    scanf("%d", &n);
    n += 1;
    int* s = new int[n];
    int* l = new int[n];
    int* b = new int[n];
    int* p = new int[n];

    p[0] = 0;
    for (int i = 1; i < n; i++) {
        scanf("%d", &p[i]);
    }
    Compress(n - 1, p, s, l, b);
    cout << s[n - 1] << endl;
    return 0;
}