随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Pku 3134 Power Calculus (BFS)

问题描述:
给定初始的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;

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, 
-1sizeof(Min) );
    memset(coun, 
0sizeof(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;
}




posted on 2009-02-16 20:59 英雄哪里出来 阅读(619) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理