題目描述

單詞接龍是一個與我們經(jīng)常玩的成語接龍相類似的游戲，現(xiàn)在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現(xiàn)兩次），在兩個單詞相連時，其重合部分合為一部分，例如?beastbeast和astonishastonish，如果接成一條龍則變?yōu)閎eastonishbeastonish，另外相鄰的兩部分不能存在包含關(guān)系，例如atat?和?atideatide?間不能相連。

輸入輸出格式

輸入格式：

?

輸入的第一行為一個單獨的整數(shù)nn?(n \le 20n≤20)表示單詞數(shù)，以下nn?行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在.

?

輸出格式：

?

只需輸出以此字母開頭的最長的“龍”的長度

?

輸入輸出樣例

輸入樣例#1：?復(fù)制

5 at touch cheat choose tact a

輸出樣例#1：?復(fù)制

23

說明

（連成的“龍”為atoucheatactactouchoose）

NOIp2000提高組第三題

作者:?Hinanawi_Feng

#include<cstdio> #include<iostream> #include<string> #include<cmath> using namespace std; int n;//單詞數(shù) string tr[30];//存儲字符串 int yc[30][30];//兩個字母的最小重疊部分 int vis[30];//判斷單詞使用頻率. int mt(int x, int y) //mt函數(shù)，返回x單詞后連接一個y單詞的最小重疊部分 {bool pp = true;int ky = 0;for(int k = tr[x].size() - 1; k >= 0; k--) //要比較size次，從x單詞尾部向前看看最小重疊部分是從哪里開始的，以為因為是倒著來，所以保證是最小的{for(int kx = k; kx < tr[x].size(); kx++){if(tr[x][kx] != tr[y][ky++]){pp = false;break;}}if(pp == true) //如果說當(dāng)前以k為開頭的前一個單詞后綴 ,是后面單詞的前綴，就馬上返回重疊部分。（tr[x].size()-k是找出來的規(guī)律）{return tr[x].size() - k;}ky = 0;pp = true; //不行就繼續(xù)}return 0; }//可能這里有點難理解。可以手動模擬一下char ch;//開頭字母 int ans = -1; //答案 int an = 0; //每次搜到的當(dāng)前最長串void dfs(int p) //p為尾部單詞編號(p的后綴就是“龍”的后綴，因為p已經(jīng)連接到”龍“后面了) {bool jx = false;for(int j = 1; j <= n; j++){if(vis[j] >= 2)continue;//使用了兩次就跳過if(yc[p][j] == 0)continue;//兩單詞之間沒有重合部分就跳過if(yc[p][j] == tr[p].size() || yc[p][j] == tr[j].size())continue;//兩者存在包含關(guān)系就跳過an += tr[j].size() - yc[p][j]; //兩單詞合并再減去最小重合部分vis[j]++;//使用了一次jx = true; //標(biāo)記一下當(dāng)前已經(jīng)成功匹配到一個可以連接的部分dfs(j); //接上去an -= tr[j].size() - yc[p][j]; //回溯，就要再減回去那一部分長度vis[j]--;//回溯,使用--}if(jx == false) //jx==false說明不能再找到任何一個單詞可以相連了{ans = max(ans, an); //更新ans}return; }int main() {scanf("%d", &n);for(int i = 1; i <= n; i++)cin >> tr[i];cin >> ch;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){yc[i][j] = mt(i, j);}}//預(yù)處理yc數(shù)組。yc[i][j]就表示，i單詞后連接一個j單詞的最小重疊部分//比如 i表示at,j表示att. yc[i][j]就為2 但是yc[j][i]就為0.//預(yù)處理是一個關(guān)鍵for(int i = 1; i <= n; i++) //從頭到尾看一下有沒有以指定開頭字母為開頭的單詞{if(tr[i][0] == ch) //如果有，就以當(dāng)前單詞為基準(zhǔn)進行搜索。{vis[i]++;//使用過一次an = tr[i].size(); //更新當(dāng)前串長度dfs(i);//接上vis[i] = 0; //消除影響}}printf("%d", ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的洛谷——P1019 单词接龙的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。