• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 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 英雄哪里出來 閱讀(634) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            色综合久久综合中文综合网| 色成年激情久久综合| 久久免费99精品国产自在现线| 久久er国产精品免费观看8| 四虎国产精品免费久久| 中文无码久久精品| 久久精品国产99国产精品| 99精品久久久久久久婷婷| 亚洲国产精久久久久久久| 亚洲国产精品无码久久久秋霞2| 久久青青草原国产精品免费 | 久久久久国产一级毛片高清版| 精品人妻伦九区久久AAA片69| 新狼窝色AV性久久久久久| 久久九九免费高清视频| 久久超乳爆乳中文字幕| 亚洲精品久久久www| segui久久国产精品| 欧美黑人又粗又大久久久| 亚洲欧洲久久久精品| 国产精品美女久久久久av爽| 国产精品9999久久久久| 亚洲中文久久精品无码ww16| 欧美久久天天综合香蕉伊| 亚洲国产精品久久久久网站| 国产精品久久精品| 久久精品国产亚洲AV香蕉| 7777精品久久久大香线蕉| 久久人人爽人人爽人人片AV高清| 久久国产乱子伦精品免费午夜| 久久青草国产手机看片福利盒子 | 久久久黄色大片| 久久精品亚洲男人的天堂| 伊人久久大香线焦综合四虎| 国产精品天天影视久久综合网| 久久久久免费看成人影片| 日韩精品久久久久久免费| 国内精品人妻无码久久久影院| 麻豆一区二区99久久久久| 国产成人久久AV免费| 久久久久久亚洲精品成人|