【搜索】單詞遊戲 words 解題報告

Title: 單詞遊戲

Input: words.in

Output: words.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

【問題描述】

慧慧和南南在玩一個單詞遊戲。

他們輪流說出一個僅包含母音字母的單詞，並且後一個單詞的第一個字母必須與前一個單詞的最後一個字母一致。

遊戲可以從任何一個單詞開始。

任何單詞禁止說兩遍，遊戲中只能使用給定詞典中含有的單詞。

遊戲的複雜度定義為遊戲中所使用的單詞長度總和。

編寫程序，求出使用一本給定的詞典來玩這個遊戲所能達到的遊戲最大可能複雜度。

【輸入】

輸入文件的第一行，表示一個自然數N（1≤N≤16），N表示一本字典中包含的單詞數量。以下的每一行包含字典中的一個單詞，每一個單詞是由字母A，E，I，O和U組成的一個字元串，每個單詞的長度將小於等於100，所有的單詞是不一樣的。

【輸出】

輸出文件僅一行，表示該遊戲的最大可能複雜度。

【樣例】

words.in

5

IOO

IUUO

AI

OIOOI

AOOI

words.out

16

【分析】

我一開始以為數據規模很小，隨便亂搞一個dfs都能AC，後來～@#￥%……&

就這一破題，弄了半小時才AC。

我的做法是這樣的，先構圖，如能第i個單詞和第j個單詞能連上，則連一條邊(i,j)～就這樣，構出一個有向圖來，最後加一個超級源S和超級匯T，再引2*N條邊：(S,i)、(i、T),(1<=i<=N)。

構完圖後，就是從源點(S)開始『遞』，直到搜到匯點(T)才『歸』。最後輸出最優解即可。

不過，我這樣做只能A掉6～7組，還有3～4組會TLE。

其實加個優化即可，記錄一下有即可有效單詞(即可以和別的單詞構成『串』的單詞)，若記這個數為P，遞歸時只要遞歸了P個單詞即可輸出結果並立即結束程序(exit)。

這樣就能大幅提高速度，我的機子CPU是 Intel Core i3，跑完10組數據共0.01sec不到。 

【我的代碼】

裸代碼RawCode

C++语言: Codee#25425

001 /*
002 *Problem: 單詞遊戲『words』 http://cogs-new.appspot.com/t/374
003 *Author: Yee-fan Zhu
004 *Method: Depth First Search
005 */
006 #include <cstdio>
007 #include <cstring>
008 #include <vector>
009 #define openfile(str) freopen(str".in","r",stdin),freopen(str".out","w",stdout)
010 #define clr(arr,val) memset(arr,val,sizeof(val))
011 using namespace std;
012 typedef vector<int> Vector;
013 const int MAXN=16+2+1;
014 int N;
015 Vector Map[MAXN],Val[MAXN];
016 char Word[MAXN][101];
017 int Len[MAXN];
018 int S,T;
019 int Ans=0;
020 int flag[MAXN];
021 int Tot;
022 int used[MAXN];
023
024 void init()
025 {
026     scanf("%d\n",&N);
027     for(int i=1;i<=N;i++)
028     {
029         scanf("%s\n",Word[i]);
030         Len[i]=strlen(Word[i]);
031         if(Ans<Len[i])
032             Ans=Len[i];
033     }
034     S=N+1,T=N+2;
035     for(int i=1;i<=N;i++)
036     {
037         Map[S].push_back(i);
038         Val[S].push_back(Len[i]);
039     }
040    
041     Tot=N;
042     char a,b;
043     for(int i=1;i<=N;i++)
044     {
045         for(int j=1;j<=N;j++)
046         {
047             if(i==j)
048                 continue;
049             a=Word[i][Len[i]-1];
050             b=Word[j][0];
051             if(a!=b)
052                 continue;
053             Map[i].push_back(j);
054             Val[i].push_back(Len[j]);
055            
056             used[i]=1;
057             used[j]=1;
058         }
059     }
060     for(int i=1;i<=N;i++)
061     {
062         Map[i].push_back(T);
063         Val[i].push_back(0);
064     }
065    
066     for(int i=1;i<=N;i++)
067         if(!used[i])
068             Tot--;
069     used[T]=1;
070 }
071
072 void dfs(int num,int pos,int val)
073 {
074     if(pos==T)
075     {
076         if(val>Ans)
077             Ans=val;
078        
079        
080         if(num==Tot+1)
081         {
082             printf("%d\n",Ans);
083             exit(0);
084         }
085        
086        
087         return;
088     }
089
090     flag[pos]=1;
091     for(unsigned int i=0;i<Map[pos].size();i++)
092     {
093         int nxt=Map[pos][i];
094         int nvl=Val[pos][i];
095         if(flag[nxt])
096             continue;
097         if(!used[nxt])
098             continue;
099         dfs(num+1,nxt,val+nvl);
100     }
101     flag[pos]=0;
102 }
103
104 int main()
105 {
106     openfile("words");
107     init();
108     clr(flag,0);
109     dfs(0,S,0);
110     fprintf(stdout,"%d\n",Ans);
111     return 0;
112 }