• <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;
              }

            以上代碼超時。完全可以剪枝。
            舉個例子
            abc
            cbd
            dbm
            dbacmdp
            我的程序一直搜啊搜,每次搜完都重新開始。比如在以a開頭后,搜到c,下次再搜索時直接利用c的結果,這是深搜的特點決定的!!!
            *************************
            這種類似的有序搜索都可以用     *  備忘錄方法*
            **************************
            #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;//相當于備忘錄,而且無需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;
              }

            因為I!=pre又錯了幾下。
            以后debug盡量自己用眼睛看,更省時間!!!!!!!!!

            posted on 2009-07-05 12:33 luis 閱讀(330) 評論(0)  編輯 收藏 引用 所屬分類: 搜索給我啟發題
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            文章分類

            文章檔案

            友情鏈接

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产精品一区二区久久hs| 久久综合狠狠综合久久| 国产国产成人精品久久| 青青青青久久精品国产h| 久久综合成人网| 伊人久久精品无码二区麻豆| 久久精品a亚洲国产v高清不卡| 国产亚洲成人久久| 精品久久久中文字幕人妻| 久久青草国产手机看片福利盒子| 久久不射电影网| 亚洲中文字幕无码久久精品1| 久久久一本精品99久久精品66| 久久免费小视频| 久久精品综合网| 一级做a爰片久久毛片毛片| 久久综合九色综合久99| 久久久精品2019免费观看| 精品国产青草久久久久福利| 久久综合给合久久狠狠狠97色| 久久99久久无码毛片一区二区| 久久综合狠狠综合久久综合88| Xx性欧美肥妇精品久久久久久| 久久精品国产久精国产| 中文字幕无码av激情不卡久久| 久久精品视频免费| 色婷婷久久综合中文久久蜜桃av| 精品免费久久久久国产一区| 99精品国产在热久久| 久久国产亚洲精品无码| 久久久久亚洲AV片无码下载蜜桃| 精品久久久久久无码中文野结衣 | 久久精品无码一区二区三区免费 | 精品久久久久久无码专区不卡| 久久99精品久久久大学生| 久久精品国产清自在天天线| 99热精品久久只有精品| 亚洲伊人久久大香线蕉苏妲己| 九九99精品久久久久久| 四虎国产精品免费久久久| 久久亚洲综合色一区二区三区|