//圖像壓縮問題

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define N 100
int s[N], l[N], b[N];

int length(int n)
{
	int k=0;
	while(n>0)
	{
		k++;
		n/=2;
	}
	return k;
}

void Compress(int n, int p[])
{
	int Lmax=256,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;
	}
}

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

void Output(int n)
{
	cout<<"The optimal value is "<<s[n]<<endl;
	int m=0;
	Traceback(n, m);
	s[m]=n;
	cout<<"Decompose into "<<m<<" segments:"<<endl;
	for(int j=1; j<=m; j++)
	{
		l[j]=l[s[j]];
		b[j]=b[s[j]];
	}
	for(j=1; j<=m; j++) cout<<l[j]<<'\t'<<b[j]<<endl;
}

void main()
{
	srand(time(0));
	int i, p[N];
	for(i=0; i<N; i++) p[i]=rand()%256;
	Compress(N, p);
	Output(N);
}