给定像素序列，求出最优分段及所占字节数。

输出s[0],s[1],s[2].......及l[1],l[2],l[3].......的计算过程，并给出最终解。

例如实例1最后输出:

最优分段是：<10,12,15>,<255>,<1,2>     总存储位数为：57

给定实例1：P=<10,12,15,255,1,2>

给定实例2：P=<1,1,0,1,233,28,58,60>

代码如下

#include <iostream>
#include <cstdio>
using namespace std; 
//int p[100]={0,10,12,15,255,1,2};//第一组测试数据 
int p[100]={0,1,1,0,1,233,28,58,60};//第二组测试数据 
int s[100]={0},l[100]={0},b[100][100]={0};//把b[i-j-1,i]，即函数B结果存储起来避免重复调用 
int cell(int m)//返回最大灰值所占的位数 
{
	return m<16?
	(m<2?1:(m<4?2:(m<8?3:4))):
	(m<32?5:(m<64?6:(m<128?7:8)));
}
int B(int k,int i) //求b的值
{
	int maxPk=p[k++];//设第首个为最大，再逐个比较 
	for(int t=k;t<=i;t++)
		if(p[t]>maxPk) maxPk=p[t];//找出maxPk，最大灰值
	return maxPk;
	//ceil(log2(maxPk+1));//返回log2(maxPk+1),向上取整，即最大灰值所占的位数 
} 

void TrackResult(int k,int n)//递归输出结果，后序遍历  
{
	if(l[k]) 
	{
		TrackResult(k-l[k],n);//后序遍历 
		for(int i=k-l[k]+1;i<=k;i++)
			if(i==k-l[k]+1) cout<<'<'<<p[i];
			else cout<<','<<p[i];
		cout<<'>';
		if(k!=n) cout<<',';//输出逗号隔开，末尾不用 
	}
}
void Track(int k,int n,int duan)//递归输出过程，后序遍历  
{
	if(l[k]) 
	{
		Track(k-l[k],n,duan+1);//后序遍历 
		cout<<"第"<<duan+1<<"段的像素个数为："<<l[k];//输出段数与像素个数
		cout<<"  每个像素的存储位数为："<<cell(b[k-l[k]+1][k])<<endl;//输出最大灰值占的位数
	}
	else
	{
		cout<<"像素序列被分成:"<<duan<<"段"<<endl;//输出总段数
	}
}
void compress(int n)//动态规划压缩 
{
	cout<<"像素序列是：P=<"<<p[1];
	for(int i=2;i<=n;i++)
		cout<<','<<p[i];
	cout<<'>'<<endl;
	printf("s[0]=%d\n",s[0]);
	for(int i=1;i<=n;i++)
	{
		int Mi=min(i,256);//256为最大段长 
		
		//类似于s[2]=min{s[2-1]+1*b[2-1+1,2],s[2-2]+2*b[2-2+1,2]}+11格式 
		printf("s[%d]=min{s[%d-1]+1*b[%d-1+1,%d]",i,i,i,i);//输出第一个数据 
		for(int j=2;j<=Mi;j++)
			printf(",s[%d-%d]+%d*b[%d-%d+1,%d]",i,j,j,i,j,i);//输出数据
		cout<<"}+11"<<endl;//换行 
		
		//类似于=min{s[1]+b[2],s[0]+2*b[1,2]}+11格式 
		printf("    =min{s[%d]+1*b[%d,%d]",i-1,i,i);//输出第一个数据 
		for(int j=2;j<=Mi;j++)
			printf(",s[%d]+%d*b[%d,%d]",i-j,j,i-j+1,i);//输出数据 
		cout<<"}+11"<<endl;//换行
		
		//类似于=min{15+4,0+2*4}+11的格式输出
		b[i][i]=B(i,i);//调用函数B计算并记录b[i-1+1,i],记录下来,避免重复调用,降低时复度 
		printf("    =min{%d+%d*%d",s[i-1],1,cell(b[i][i]));//输出第一个数据s[i-1]+j*b[i-j+1][i]
		for(int j=2;j<=Mi;j++)
		{
			b[i-j+1][i]=B(i-j+1,i);//调用函数B计算并记录b[i-j+1,i]，避免重复调用，影响时复度 
			printf(",%d+%d*%d",s[i-j],j,cell(b[i-j+1][i]));//输出数据s[i-1]+j*b[i-j+1][i]
		}
		cout<<"}+11"<<endl;

		//类似于=min{31,35,39,32}+11的格式输出，并找出最小s[i]
		s[i]=s[i-1]+cell(b[i][i]); 
		l[i]=1;
		printf("    =min{%d",s[i-1]+cell(b[i][i]));
		for(int j=2;j<=Mi;j++)
		{
			printf(",%d",s[i-j]+j*cell(b[i-j+1][i]));//输出数据 
			if(s[i-j]+j*cell(b[i-j+1][i])<s[i])//找到更小的位数 
			{
				s[i]=s[i-j]+j*cell(b[i-j+1][i]); //记录更小的位数 
				l[i]=j;//记录这一段的像素个数 
			}
		}
		s[i]+=11;//最后找出的最小s[i]加11 
		cout<<"}+11"<<"       ";
		cout<<b[i-l[i]+1][i]<<"<2^"<<cell(b[i-l[i]+1][i])<<endl;//输出最大灰值占的位数 
		printf("    =%d		l[%d]=%d\n\n",s[i],i,l[i]);//输出s[i]和l[i] 
	}
	Track(n,n,0);//回溯追踪输出过程
	cout<<endl<<"最优分段是:";
	TrackResult(n,n); //回溯追踪结果
	cout<<"   存储位数为"<<s[n]<<endl;//输出得出的最小空间 
}
int main()
{
	//int n=6;//第一组测试数据
	int n=8;//第二组测试数据 
	compress(n);//调用压缩函数 
}

运行结果