问题描述:
给定初始的x,可以通过乘法将其变为x^2,再变为x^4,x^8,x^16,x^32,也可以用除法,x^31 = x^32 / x,但是操作数必须是已经计算出来的数,给定一个指数,要求得到这个指数的最小步数。比如31输出6(1 2 4 8 16 32 31)。
这道题目是去年参加whu邀请赛的时候遇到的,当时是热身赛题目,后来一直没想通,看了威士忌的解题报告,是用迭代加深写的,后来想了想越看越象BFS,就开始敲了,可是973这组数据总是输出13,搞了半天把路径输出来发现了弊病所在,就是在两个搜到相同的值的步数是一样的时候,不能略过,因为路径不同可能导致最后的结果不同,但是记录路径再比较就太冗繁了,我的策略是将步数相同的值多搜几次取最优,竟然过了,344MS。不过时限开了5000MS,怎么搜都可以过的。
具体思路:
对一个结构体进行Bfs,记录路径,每次搜到u这个数的当前步数小于先前搜出的数则入队,如果等于,也入队,并且u这个数的计数器+1,直到达到某个limit则不再搜(后来刷了下,limit取6的时候可以达到74MS)保存最优值即可。
代码如下:
#include <iostream>
#include <queue>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int stack[30];
int x;
int top;
int step;
}temp, tt, buf;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n;
int Min[2001];
int coun[2001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
queue < point > q;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int i, j, k;
memset(Min, -1, sizeof(Min) );
memset(coun, 0, sizeof(coun));
Min[1] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
temp.top = 0;
temp.stack[ temp.top++ ] = 1;
temp.step = 0;
temp.x = 1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
q.push( temp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(!q.empty())
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
temp = q.front();
q.pop();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < temp.top; i++)
{
for(j = -1; j <= 1; j += 2)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
tt = temp;
tt.step = temp.step + 1;
int u = tt.x + tt.stack[i] * j;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(u <= 1 || u > 2000)
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(tt.step == Min[u])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
coun[u] ++;
if(coun[u] > 10)
continue;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
tt.stack[ tt.top ++ ] = u;
tt.x = u;
q.push( tt );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(Min[u] == -1 || tt.step < Min[u])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Min[u] = tt.step;
tt.stack[ tt.top ++ ] = u;
tt.x = u;
q.push( tt );
}
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while( scanf("%d", &n) != EOF && n )
{
printf("%d\n", Min[n] );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)