• <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>
            posts - 195,  comments - 30,  trackbacks - 0
            Status In/Out TIME Limit MEMORY Limit Submit Times Solved Users JUDGE TYPE
            stdin/stdout 3s 8192K 439 74 Standard

            Io and Ao are playing a word game. They say a word in the dictionary by turns. The word in the dictionary only contains lowercase letters. And the end character of the former said word should be the same as the start character of the current said word. They can start the game from any word in the dictionary. Any word shouldn't be said twice. Now, we define the complexity of the game that is the sum length of all words said in the game. Give you a dictionary, can you tell me the max complexity of this word game?

            Input

            The first line contains a single positive integer n(0 < n <=12). Next n lines are n words in the dictionary. The length of each word will not exceed 100.

            Output

            A single integer represents the complexity of the game.

            Sample Input

            3
            joj
            jlu
            acm
            6
            cctv
            redcode
            lindong
            we
            love
            programming
            3
            daoyuanlee
            come
            on
            

            Sample Output

            6
            11
            10
            

            Problem Source: provided by loon

            #include<iostream>
            #include<cstdlib>
            using namespace std;
            struct S
            {
             string a;
             char begin;
             char end;
             int length;
             }s[13];
             int visited[13];
            int temp; 
            void search(int a,int num,int pre)
             {
              
              for(int i=0;i<num;i++ )
              {
               if(s[i].begin==s[pre].end&&visited[i]==0)
               {
                visited[i]=1;
                search(a+s[i].length,num,i);
                if(a+s[i].length>temp)temp=a+s[i].length;
                visited[i]=0;
               }
              }
             }
              int main()
              {
              freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
               int num;
               while(cin>>num)
               {
                int i;
              temp=0;
              for( i=0;i<num;i++)
              {
               cin>>s[i].a;
               s[i].length=(s[i].a).size();
               s[i].begin=(s[i].a)[0];
               s[i].end=(s[i].a)[s[i].length-1];
               if(s[i].length>temp)
               temp=s[i].length;
                 }
              for(i=0;i<num;i++) 
                 {
               memset(visited,0,sizeof(visited));
               visited[i]=1;
               search(s[i].length,num,i);
              }
              cout<<temp<<endl;
             }

              //system("PAUSE");
              return   0;
              }

            以上代碼超時(shí)。完全可以剪枝。
            舉個(gè)例子
            abc
            cbd
            dbm
            dbacmdp
            我的程序一直搜啊搜,每次搜完都重新開始。比如在以a開頭后,搜到c,下次再搜索時(shí)直接利用c的結(jié)果,這是深搜的特點(diǎn)決定的!!!
            *************************
            這種類似的有序搜索都可以用     *  備忘錄方法*
            **************************
            #include<iostream>
            #include<cstdlib>
            using namespace std;
            int num;
            struct S
            {
             string a;
             char begin;
             char end;
             int length;
             }s[13];
             int visited[13];
            int temp;
            int sum[13]; 
            int search(int pre)//·µ»Ø´ÓpreµãÒÔºóµÄ×ܵÄÖµ
             {
              int j=s[pre].length,k=0;
              for(int i=0;i<num;i++ )
              {
               if(s[i].begin==s[pre].end&&visited[i]==0&&i!=pre)//必須要有I!=pre
               {
                visited[i]=1;
                k=search(i)+s[pre].length;
                if(k>j)j=k;
               }
               else
               {
                if(s[i].begin==s[pre].end&&i!=pre)//必須要有i!=pre
                return sum[i]+s[pre].length;//相當(dāng)于備忘錄,而且無需visited[i]=0;
               }
              }
              sum[pre]=j;
              return j;
             }
              int main()
              {
             freopen("s.txt","r",stdin);
              freopen("key.txt","w",stdout);
               while(cin>>num)
               {
                int i,j;
              temp=0;
              j=0;
              for( i=0;i<num;i++)
              {
               cin>>s[i].a;
               s[i].length=(s[i].a).size();
               s[i].begin=(s[i].a)[0];
               s[i].end=(s[i].a)[s[i].length-1];
               if(s[i].length>temp)
               temp=s[i].length;
                 }
              for(i=0;i<num;i++) 
                 {
               memset(visited,0,sizeof(visited));
                        memset(sum,0,sizeof(sum));
               visited[i]=1;
               j=search(i);
               if(j>temp)
               temp=j;
              }
              cout<<temp<<endl;
             }

              //system("PAUSE");
              return   0;
              }

            因?yàn)镮!=pre又錯(cuò)了幾下。
            以后debug盡量自己用眼睛看,更省時(shí)間!!!!!!!!!

            posted on 2009-07-05 12:33 luis 閱讀(328) 評論(0)  編輯 收藏 引用 所屬分類: 搜索給我啟發(fā)題
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久婷婷国产综合精品| 国产精品一区二区久久| 久久男人AV资源网站| 久久久WWW成人免费精品| 欧美午夜A∨大片久久 | 久久99国产精品成人欧美| 久久九九久精品国产免费直播| 伊人久久大香线蕉综合网站| 精品久久久噜噜噜久久久| 久久久不卡国产精品一区二区| 久久综合九色综合网站| 久久93精品国产91久久综合| 久久婷婷成人综合色综合| 国产精品免费久久| 无码专区久久综合久中文字幕| 国产999精品久久久久久| 色偷偷久久一区二区三区| 久久久久97国产精华液好用吗| 久久久久国产精品熟女影院| 四虎久久影院| 久久国产精品国语对白| 久久超碰97人人做人人爱| 久久精品青青草原伊人| 热RE99久久精品国产66热| 日本免费久久久久久久网站| 国产美女久久精品香蕉69| 亚洲午夜久久久久妓女影院| 亚洲成av人片不卡无码久久| 精品久久久久久无码国产| 91精品日韩人妻无码久久不卡| 丁香狠狠色婷婷久久综合| 久久久久人妻一区精品色| 精品综合久久久久久97| 久久天天躁狠狠躁夜夜不卡 | 久久久久久精品成人免费图片| 久久精品?ⅴ无码中文字幕| www亚洲欲色成人久久精品| 久久精品国产99国产电影网| 国内精品久久人妻互换| 99久久成人国产精品免费| 俺来也俺去啦久久综合网|