摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DP

首先先建出連接的關係圖 (編號十進制)

它因為是0000->1111 (n個0 n個1)  要走n步

但是每次只能走只差1個bits,也就是,將編號轉成二進制時

將1剔除掉,或者將0的位置換成1,

若只能走n步的話,由此可以推得

1111->0000 (n個0 n個1) 

是依照順序剔除掉 1 但是順序隨機

這樣才能達到目的

如果是這樣的話  只要逐步更新  即可達到最佳解

/*************************************************************/

#include<stdlib.h>
#include<stdio.h>
int map[600][20]={0},maptop[600]={0};
void make()
{
   int a;
   for(a=1;a<=512;a++)
       {
          int t=a,b=1;
          while(t)
              {
                 if(t%2==1)
                    map[a][maptop[a]++]=a-b;
                 t=t/2;
                 b=b*2;
              }
       }
}
main()
{
   make();
       int N,Nn[10]={1,2,4,8,16,32,64,128,256,512};
   while(scanf("%d",&N)==1&&N)
        {
          
           int a,b,c;
           int data[600]={0};
           for(a=0;a<Nn[N];a++)
               scanf("%d",&data[a]);
              
           int path[600]={0};
           for(a=0;a<Nn[N];a++)
              for(b=0;b<maptop[a];b++)
                 {
                    int temp=path[map[a][b]]+data[a];
                    if(path[a]<temp)   path[a]=temp;
                 }
           printf("%d\n",path[Nn[N]-1]+data[0]);
        }
  return 0;
}