用本班數(shù)學(xué)神牛高瑞陽的話說“這是一道水題”。原題是數(shù)學(xué)題，要求求解n=3時的最小步數(shù)。
據(jù)說高同學(xué)用五分鐘AC原題，并證明：有且僅有一種方案解決這個問題。
而本題作為usaco上的一道題目，必要的數(shù)學(xué)功底自然是必要的，但我們也應(yīng)以O(shè)Ier的思維方式來解決次題。
主體是搜索，加上狀態(tài)壓縮的DFS。（用show來調(diào)試，逐步寫成4個操作，非常順利。）
由于有且僅有一種方案解決這個問題，那么大量的可行性剪枝是可以顯然得到的。
顯然，w向右移動之后，再向左移是不符合最優(yōu)性原理的，所以我們只考慮w右移。同理，只考慮b的左移。
（高神牛的那個結(jié)論可以說明，只要不是最優(yōu)性的操作，必然是不可行的操作）
此時的搜索數(shù)已經(jīng)很小了，每個節(jié)點的分支數(shù)<2,基本上可以可以合理的通過此題。
（根據(jù)我的推測時間復(fù)雜度O（2^(2*n)））
又因為，有且僅有一種方案解決這個問題，所以我們輸出時不用考慮答案的順序。只要注意換行就行了。
代碼
/*
USER:zyn19961
LANG:C++
TASK:shuttle
*/
#include<cstdio>
#include<cstring>
int n;
bool flag=false;
int use[100001];
int goal=0;
void show(int m,int t);
void work(int i,int place,int m);
int main(){
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w",stdout);
int mm=0;
scanf("%d",&n);
goal=1<<n;goal--;goal<<=(n+1);
work(1,n+1,(1<<n)-1);
fclose(stdin);
fclose(stdout);
return 0;
}
void work(int i,int place,int m){
int t;
//show(m,place);
if(flag)return ;
if(m==goal){
flag=true;
for(int j=1;j<=i-2;j++){
if(j%20==0)
printf("%d\n",use[j]);
else
printf("%d ",use[j]);
}
printf("%d\n",use[i-1]);
return;
}
if(m&(1<<(place-2))&&place>=2){
use[i]=place-1;
t=m-(1<<(place-2));
t+=(1<<(place-1));
work(i+1,place-1,t);
}
if(!(m&(1<<(place)))&&place<=n*2){
use[i]=place+1;
work(i+1,place+1,m);
}
if((m&(1<<(place)))&&(!(m&(1<<(place+1))))&&place<=2*n-1){
use[i]=place+2;
work(i+1,place+2,m);
}
if((m&(1<<place-3))&&(!(m&(1<<(place-2))))&&place>=3){
use[i]=place-2;
t=m-(1<<(place-3));
t+=1<<(place-1);
work(i+1,place-2,t);
}
}
void show(int m,int t){
for(int i=0;i<=t-2;i++)
printf("%d",(m&(1<<i))>>i);
printf("*");
for(int i=t;i<=n*2;i++)
printf("%d",(m&(1<<i))>>i);
printf("\n");
}關(guān)于那個非常非常重要的結(jié)論，其實我也想到了，如果想要證明的話，去找高神牛吧！
感謝二中溫暖的辦公室和無線網(wǎng)絡(luò)。
12.12 by zyn