問題描述：
給定初始的x，可以通過乘法將其變?yōu)閤^2，再變?yōu)閤^4，x^8，x^16，x^32，也可以用除法，x^31 = x^32 / x，但是操作數(shù)必須是已經(jīng)計(jì)算出來的數(shù)，給定一個(gè)指數(shù)，要求得到這個(gè)指數(shù)的最小步數(shù)。比如31輸出6（1 2 4 8 16 32 31）。
這道題目是去年參加whu邀請賽的時(shí)候遇到的，當(dāng)時(shí)是熱身賽題目，后來一直沒想通，看了威士忌的解題報(bào)告，是用迭代加深寫的，后來想了想越看越象BFS，就開始敲了，可是973這組數(shù)據(jù)總是輸出13，搞了半天把路徑輸出來發(fā)現(xiàn)了弊病所在，就是在兩個(gè)搜到相同的值的步數(shù)是一樣的時(shí)候，不能略過，因?yàn)槁窂讲煌赡軐?dǎo)致最后的結(jié)果不同，但是記錄路徑再比較就太冗繁了，我的策略是將步數(shù)相同的值多搜幾次取最優(yōu)，竟然過了，344MS。不過時(shí)限開了5000MS，怎么搜都可以過的。
具體思路：
對一個(gè)結(jié)構(gòu)體進(jìn)行Bfs，記錄路徑，每次搜到u這個(gè)數(shù)的當(dāng)前步數(shù)小于先前搜出的數(shù)則入隊(duì)，如果等于，也入隊(duì)，并且u這個(gè)數(shù)的計(jì)數(shù)器+1，直到達(dá)到某個(gè)limit則不再搜（后來刷了下，limit取6的時(shí)候可以達(dá)到74MS）保存最優(yōu)值即可。
代碼如下：
#include <iostream>
#include <queue>
using namespace std;
struct point
{
int stack[30];
int x;
int top;
int step;
}temp, tt, buf;
int n;
int Min[2001];
int coun[2001];
queue < point > q;
int main()
{
int i, j, k;
memset(Min, -1, sizeof(Min) );
memset(coun, 0, sizeof(coun));
Min[1] = 0;
temp.top = 0;
temp.stack[ temp.top++ ] = 1;
temp.step = 0;
temp.x = 1;
q.push( temp );
while(!q.empty())
{
temp = q.front();
q.pop();
for(i = 0; i < temp.top; i++){
for(j = -1; j <= 1; j += 2)
{
tt = temp;
tt.step = temp.step + 1;
int u = tt.x + tt.stack[i] * j;
if(u <= 1 || u > 2000)
continue;
if(tt.step == Min[u])
{
coun[u] ++;
if(coun[u] > 10)
continue;
tt.stack[ tt.top ++ ] = u;
tt.x = u;
q.push( tt );
}
if(Min[u] == -1 || tt.step < Min[u])
{
Min[u] = tt.step;
tt.stack[ tt.top ++ ] = u;
tt.x = u;
q.push( tt );
}
}
}
}
while( scanf("%d", &n) != EOF && n ){
printf("%d\n", Min[n] );
}
return 0;
}