本文共 1052 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

给出n个字符串，两个字符串如果前一个的尾与后一个的首相同，那么可以相连，最后得到的字符串要满足首尾相同，问最长的符合要求的字符串的长度是多少。

题目分析：

• 定义状态dp[i][j]代表以i开头以j结尾的最长的字符串的长度，具体转移看代码，水题不解释。

  ---

AC代码：

#include 
   
    #include 
    
     #include 
     
      #define MAX 500007using namespace std;int n;char s[MAX][12];int len[MAX];int dp[30][30];int main ( ){    while ( ~scanf ( "%d" , &n ))    {        for ( int i = 0 ; i < n ; i++ )        {            scanf ( "%s" , s[i] );            len[i] = strlen ( s[i] );        }        memset ( dp , -1 , sizeof ( dp ));        for ( int i = 0 ; i < n ; i++ )        {            int x = s[i][0]-'a';            int y = s[i][len[i]-1] -'a';            for ( int j = 0 ; j < 26 ; j++ )                if ( dp[j][x] != -1 )                    dp[j][y] = max ( dp[j][x]+len[i] , dp[j][y] );             dp[x][y] = max ( dp[x][y] , len[i] );        }        int ans = 0;        for ( int i = 0 ; i < 26; i++ )            for ( int j = 0 ; j < 26 ; j++ )                if ( i == j )                    ans = max ( ans , dp[i][j] );        printf ( "%d\n" , ans );    }}
     
    
   

转载地址：http://sqvjn.baihongyu.com/