高雄市98資訊學科能力競賽 第五題:超立方體的路徑問題
作法 : 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;
}