#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
