题目链接:Click here~~
题意:
有若干个字符串,求一个最长的环,且顺序必须满足给定顺序,即后面的串只能接在前面的串的后边。
解题思路:
令dp[i][j]表示从字母 i 到字母 j 所能走过的最长长度。
设某串长度为len,则状态转移方程为dp[k][j] = max(dp[k][j],dp[k][i]+len).k∈{a,b,…z}
且要注意两点:
1、递推时,前一个状态是否合法。
2、某个串出现后,必有合法状态dp[i][j] = len。
最后循环找f[k][k]的最大值即为最长环的长度。
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; #define FileIn freopen("in.ads","r",stdin) #define FileOut freopen("out.ads","w",stdout) int main() { int n,l,r,len,f[27][27]; char str[12]; while(~scanf("%d",&n)) { memset(f,0,sizeof(f)); while(n--) { scanf("%s",str); len = strlen(str); l = str[0] - 'a'; r = str[len-1] - 'a'; for(int i=0;i<26;i++) if(f[i][l]) f[i][r] = max(f[i][r],f[i][l]+len); f[l][r] = max(f[l][r],len); } int ans = 0; for(int i=0;i<26;i++) ans = max(ans,f[i][i]); printf("%d\n",ans); } return 0; }