图像压缩问题（动态规划）

#include <iostream>
#include <cmath>
#include <stack>
#define N 6//像素个数
using namespace std;
int S[N + 1];//存储结果 
int T[N + 1];//用于追踪解
int b[N + 1][N + 1];//记录该两个下标所围区间内最大像素
void Compress(int *P, int n){
    int i, j, temp0, temp1;
    for (i = 1; i <= n; ++i) {
        b[i][i] = P[i - 1];
        temp0 = (i < 256) ? i : 256;
        S[i] = S[i - 1] + floor(log2(b[i][i]) + 1) + 11;
        T[i] = 1;
        for (j = 2; j <= temp0; ++j) {
            b[i -j + 1][i] = (b[i][i] > b[i -j + 1][i - 1]) ? b[i][i] : b[i -j + 1][i - 1];
            temp1 = S[i - j] + j * floor(log2(b[i -j + 1][i]) + 1) + 11;
            if (S[i] > temp1) {
                S[i] = temp1;
                T[i] = j;
            }
        }
    }
}
void Track(int n, stack<int> *s){
    if (n <= 0) return;
    int temp = T[n];
    s -> push(temp);
    Track(n -= temp, s);
}
int main(){
    int P[N] = {10, 12, 15, 255, 1, 2};//所要压缩的像素序列值
    Compress(P, N);
    cout<<"最优存储位数为："<<S[N]<<endl;
    stack<int> s;
    Track(N, &s);
    cout<<"分段长度分别为：";
    while (!s.empty()) {
        cout<<s.top()<<" ";
        s.pop();
    }
    cout<<endl;
    return 0;
}

原理参见 屈婉玲老师 算法设计与分析 ORZ