注：本题不一样的解法

其实这道题可以状压dp的

我们先谈一下怎么状压dp：

状态定义：

dp\left[i\right]\left[j\right]表示情况i下以j号单词结尾所能达到的最大长度

我们可以用1个长度为n的01串（即二进制）表示单词使用情况，1表示使用过，0表示未使用。

举几个栗子：

• n=4时，1101表示只使用过1，3和4号单词；
• n=5时，10010表示只使用过5号和2号单词。

注意：在我写的（不包括你）01串中，第i位表示的是第n-i+1号单词的情况原因后面会提到

状态转移方程：

其中k1...kn表示枚举n个单词，len\left[k\right]\left[j\right]表示将j号单词接在k号后面长度的增加量（可预处理）

dp部分代码

for(int i=1;i<(1<<n);i++){\\总共有2^n种使用情况
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1)))continue;\\判断j在i情况下有没有被使用过
            for(int k=1;k<=n;k++){
                if((i&(1<<(k-1)))&&len[k][j]!=-1&&dp[i][k]!=-1){\\判断能否转移：1.k在情况i下使用了 2.j能接在k后面
                    dp[i|(1<<(j-1))][j]=max(dp[i|(1<<(j-1))][j],dp[i][k]+len[k][j]);\\转移：next=i|(1<<(j-1)),now=i;
                    ans=max(ans,dp[i|(1<<(j-1))][j]);\\注意不断更新最终结果
                }
            }
        }
    }

*还有一点，本题中由于么个单词可以最多用两次，所以应该开个$2n$长度的数组，将每个单词再复制一遍**

其他没什么好说的了，详见代码。。。

#include<bits/stdc++.h>
using namespace std;
int n,len[1001][1001],dp[1<<16][17],ans;
string s[1001];
char tou;
void pre(){\\预处理len数组，有点小麻烦
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            int lenans=0;
            for(int lenth=1;lenth<min(s[i].size(),s[j].size());lenth++){
                bool flag=true;
                for(int i1=s[i].size()-lenth,j1=0;i1<=s[i].size()-1,j1<=lenth-1;i1++,j1++){
                    if(s[i][i1]!=s[j][j1]){
                        flag=false;
                        break;
                    }
                }
                if(flag==true)lenans=lenth;
                if(lenans!=0)break;
            }
            if(lenans==0)len[i][j]=-1;
            else len[i][j]=s[j].size()-lenans;
        }
    }
}
int main(){
    memset(dp,-1,sizeof(dp));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=n+1;i<=2*n;i++)s[i]=s[i-n];\\复制
    n=n*2;
    pre();\\预处理
    scanf("\n%c",&tou);\\这里得加个"\n",因为数字读入之后后面还有个换行符
    for(int i=1;i<=n;i++){\\特别处理开头单词的情况
        if(s[i][0]==tou){
            dp[1<<(i-1)][i]=s[i].size();
            ans=max(ans,dp[1<<(i-1)][i]);\\注意这里也要更新ans(我被卡过一次)
        }
    }
    for(int i=1;i<(1<<n);i++){\\开始dp
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1)))continue;
            for(int k=1;k<=n;k++){
                if((i&(1<<(k-1)))&&len[k][j]!=-1&&dp[i][k]!=-1){
                    dp[i|(1<<(j-1))][j]=max(dp[i|(1<<(j-1))][j],dp[i][k]+len[k][j]);
                    ans=max(ans,dp[i|(1<<(j-1))][j]);
                }
            }
        }
    }
    printf("%d",ans);
    return 0;\\大功告成
}