//本程序取自王曉東編著“算法分析與設計”第 83 頁，例
//圖像壓縮問題動態規劃解法

 public class Fac3_6{
    static final int lmax=16;//最大限制不得超過256，為了調試程序暫定為8
    static final int header=11;
    static int m;
   public static void compress(int []p,int []s,int[] l,int []b)
   {
     int n=p.length-1;
     s[0]=0;
     for(int i=1;i<=n;i++){
        b[i]=length(p[i]);
        System.out.println("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;
     }
   }
    private static int length(int i)
     {
       int k=1;
       i=i/2;
       while(i>0){
        k++;
        i=i/2;
       }
       return k;
     }    
           
  public static void traceback(int n,int []s,int []l)
     { 
        if(n==0)return;
        traceback(n-l[n],s,l);
        s[m++]=n-l[n];
     }
   public static void output(int s[],int l[],int[] b)
     {
       int n=s.length-1;
       System.out.println("The optimal value is "+s[n]);
       m=0;
       traceback(n,s,l);
       s[m]=n;
       System.out.println("Decomposed into "+m+" segments");
       for(int j=1;j<=m;j++){
         l[j]=l[s[j]];
         b[j]=b[s[j]];
        }
       for(int j=1;j<=m;j++)
       System.out.println("l["+j+"]"+l[j]+", b["+j+"]"+b[j]);
    } 

      public static void main(String args[])
  {
    int v1[]={0,128,128,64,64,64,32,8,8,8,128,212,211,12,7,6,90,10};
    int n1=v1.length-1;
    int []l1=new int[n1+1];
    int []b1=new int[n1+1];
    int []s1=new int[n1+1];
    compress(v1,s1,l1,b1);
    output(s1,l1,b1);
  }
}