wikioi-天梯-普及一等-dfs-1018：單詞接龍

題目描述 Description

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

輸入描述 Input Description

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

輸出描述 Output Description

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

樣例輸入 Sample Input

5

at

touch

cheat

choose

tact

a

樣例輸出 Sample Output

23    

類型：圖論  難度：2

題意：給n個單詞和一個起始字母，求以這個字母開始的單詞接龍的最大長度，規則是：1、每次單詞最多用兩次，2、接龍的前後兩個單詞部分相同，但不能是包含關系。

分析：用dfs搜尋每一種接龍情況即可，記錄每次增長的的長度（即新加的單詞除去重疊部分的長度），最後記錄總長度

注意：單詞可以自己跟自己相連，比如隻給出一個單詞eye，那麼長度為5。

代碼：

#include<iostream>
#include<cstring>
#include<vector>
#include<string>
using namespace std;

vector<string> w;
vector<int> cnt;
int n;
string st;

int cntlap(string a,string b)
{
    int la = a.length(), lb = b.length();
    for(int i=1; i<la && i<lb; i++)
    {
        string suba = a.substr(la-i,i);
        string subb = b.substr(0,i);
        if(suba == subb)
            return i;
    }
    return 0;
}

int fun(int pos)
{
    cnt[pos]++;
    int ans = 0;
    for(int i=0; i<n; i++)
    {
        if(cnt[i]>=2)
            continue;
        int lap = cntlap(w[pos],w[i]);
        if(lap>0)
        {
            int tmp = fun(i)+w[i].length()-lap;
            //cout<<w[pos]<<" "<<w[i]<<" "<<lap<<" "<<tmp<<endl;
            if(tmp > ans) ans = tmp;
        }
    }
    cnt[pos]--;
    return ans;
}

int main()
{
    cin>>n;
    w.clear();
    w.resize(n);
    for(int i=0; i<n; i++)
        cin>>w[i];
    cin>>st;
    
    int ans = 0;
    for(int i=0; i<n; i++)
    {
        if(w[i][0]==st[0])
        {
            cnt.assign(n,0);
            int tmp = fun(i)+w[i].length();
            if(tmp>ans) ans = tmp;
        }
    }
    cout<<ans<<endl;
}