題目描述

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

輸入輸出格式

輸入格式：

?

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

?

輸出格式：

?

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

?

輸入輸出樣例

輸入樣例#1：
5 at touch cheat choose tact a 輸出樣例#1：
23 （連成的“龍”為atoucheatactactouchoose） #include<iostream> #include<cstdio> #include<stdio.h> #include<cmath> #include<string> #include<iomanip> using namespace std; string a[21]; int use[21]; int n,shou,ans=1,the; void dfs(int s) {the=max(the,ans);for(int i=1;i<=n;i++){if(use[i]<2){for(int j=0;j<a[s].length();j++){if(a[i][0]==a[s][j]){int x,y;x=j;y=0;while(a[i][y]==a[s][x]&&x<a[s].length()){x++;y++;}if(x>=a[s].length()){ans=ans+a[i].length()-y;use[i]++;dfs(i);use[i]--;ans=ans-a[i].length()+y;}}}}} } int main() {cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cin>>a[0];dfs(0);cout<<the;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/suibingchen/p/7299923.html

總結(jié)

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

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