• <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>
            xiaoguozi's Blog
            Pay it forword - 我并不覺的自豪,我所嘗試的事情都失敗了······習(xí)慣原本生活的人不容易改變,就算現(xiàn)狀很糟,他們也很難改變,在過程中,他們還是放棄了······他們一放棄,大家就都是輸家······讓愛傳出去,很困難,也無(wú)法預(yù)料,人們需要更細(xì)心的觀察別人,要隨時(shí)注意才能保護(hù)別人,因?yàn)樗麄兾幢刂雷约阂裁础ぁぁぁぁ?/span>
            今天做ural 1002,題目描述:
            1002. Phone numbers
            Time Limit: 2.0 second
            Memory Limit: 16 MB

            Background

            In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign letters to digits as shown in the following picture:

            	1 ij	2 abc	3 def
            4 gh	5 kl	6 mn
            7 prs	8 tuv	9 wxy
            0 oqz
            
            This way every word or a group of words can be assigned a unique number, so you can remember words instead of call numbers. It is evident that it has its own charm if it is possible to find some simple relationship between the word and the person itself. So you can learn that the call number 941837296 of a chess playing friend of yours can be read as WHITEPAWN, and the call number 2855304 of your favourite teacher is read BULLDOG.

             

            Problem

            Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above.

            Input

            Input contains a series of tests. The first line of each test contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB. The last line of input file contains call number -1.

            Output

            Each line of output contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text "No solution.". If there are more solutions having the minimum number of words, you can choose any single one of them.

            Sample

            input
            output
            7325189087
                        5
                        it
                        your
                        reality
                        real
                        our
                        4294967296
                        5
                        it
                        your
                        reality
                        real
                        our
                        -1
                        
            reality our
                        No solution.
                        


            思路就是dp,狀態(tài)轉(zhuǎn)移是dp[i]=min(dp[i-len[j]]+1)(1<=j<=n)
            code:
            #include <iostream>
            #include 
            <string>
            #include 
            <algorithm>
            #include 
            <stack>
            #include 
            <vector>

            using namespace std;
            //#pragma comment(linker, "/STACK:16777216")

            const int N=105;
            const int M=50001;
            int dp[N];
            int pathone[N];
            int pathtwo[N];
            int hash[26]={2,2,2,3,3,3,4,4,1,1,5,5,6,6,0,7,0,7,7,8,8,8,9,9,9,0};
            vector
            <string> vec,v;
            vector
            <int> ve;
            void Init()
            {
                memset(dp,
            0,sizeof(dp));
                memset(pathone,
            0,sizeof(pathone));
                memset(pathtwo,
            0,sizeof(pathtwo));
                vec.clear();
                v.clear();
                ve.clear();
            };
            int main()
            {
                
            string ss;
                
            while(cin>>ss){
                    
            if(ss=="-1")break;
                    Init();
                    
            int n;
                    cin
            >>n;
                    
            string str;
                    
            for(int i=0;i<n;i++){
                        cin
            >>str;
                        v.push_back(str);
                        
            string tmp;
                        
            for(int j=0;j<str.size();j++){
                            tmp
            +=hash[str[j]-'a']+48;
                        }
                        vec.push_back(tmp);
                    }
                    dp[
            0]=1;
                    
            for(int i=1;i<=ss.size();++i){
                        
            for(int j=0;j<vec.size();++j){
                            
            if(i-vec[j].size()>=0&&dp[i-vec[j].size()]>0){
                                               
            if(vec[j]==ss.substr(i-vec[j].size(),vec[j].size())&&(dp[i]==0||dp[i]>dp[i-vec[j].size()]+1)){
                                    dp[i]
            =dp[i-vec[j].size()]+1;
                                    pathone[i]
            =j;
                                    pathtwo[i]
            =i-vec[j].size();
                                }
                            }
                        }
                    }
                    
            if(dp[ss.size()]==0){
                        cout
            <<"No solution.\n";
                    }
                    
            else{
                        
            int mm=ss.size();
                        
            //ve.push_back(mm);
                        while(mm!=0){
                            
            //stk.push(v[pathone[mm]]);
                            ve.push_back(mm);
                            mm
            =pathtwo[mm];
                            
                        }
                        
            for(int i=ve.size()-1;i>=0;i--){
                            
            if(i==ve.size()-1)cout<<v[pathone[ve[i]]];
                            
            else cout<<" "<<v[pathone[ve[i]]];
                        }
                        cout
            <<endl;
                    }
                }
                
            return 0;
            }
            以上code ,(Crash), 看了FAQ,相當(dāng)于STACK_OVERFLOW ,先是郁悶。。。。
            玩了花了N多時(shí)間查找哪錯(cuò)問題了。。。。
            沒辦法時(shí)加了句 i-vec[j].size()<N于是奇跡出現(xiàn)了Accepted.....汗
            于是想問下各位路過大牛,,題目明顯是i<N,i-vec[j].size()<N不是就成了句廢話了。。。。無(wú)語(yǔ).....
            我碰到類似dp,用dp[i+len[j]]>dp[i]+1 dp[i+len[j]]=dp[i]+1轉(zhuǎn)換下,就不會(huì)出現(xiàn)此問題,,而用dp[i-len[j]]+1<dp[i],dp[i]=dp[i-len[j]]+1問題就出現(xiàn)了。。。RE,所以想問下原因,,,我以保證i-len[j]>=0&&i-len[j]<N(dp[N])
            posted on 2008-04-05 16:21 小果子 閱讀(287) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Acm
            亚洲精品tv久久久久| 久久人爽人人爽人人片AV| 久久香蕉综合色一综合色88| www亚洲欲色成人久久精品| 久久亚洲国产欧洲精品一| 久久人人爽人人澡人人高潮AV| 久久性精品| 1000部精品久久久久久久久| 99久久精品九九亚洲精品| 久久天天躁狠狠躁夜夜不卡 | 久久婷婷五月综合国产尤物app| 久久精品免费一区二区| 久久99国产精品久久久| 久久久精品人妻一区二区三区蜜桃 | 亚洲人成精品久久久久| 国产福利电影一区二区三区,免费久久久久久久精 | 久久中文字幕一区二区| 久久夜色精品国产亚洲| 国产成人久久777777| 欧美亚洲色综久久精品国产| 激情久久久久久久久久| 国产精品久久网| 久久久久人妻一区精品色 | 99久久国产综合精品网成人影院| 亚洲va久久久噜噜噜久久| 久久综合伊人77777| 国产ww久久久久久久久久| 国内精品人妻无码久久久影院| 亚洲国产精品成人久久蜜臀| 国产精品成人久久久久三级午夜电影 | 久久毛片一区二区| 亚洲国产精品一区二区三区久久| 2020最新久久久视精品爱 | 国产精品免费福利久久| 亚洲精品无码久久久久sm| 久久久国产99久久国产一| 四虎国产精品免费久久| 亚洲国产天堂久久久久久| 99久久综合国产精品免费| 精品国产99久久久久久麻豆| 亚洲国产美女精品久久久久∴ |