题目链接：https://codeforces.com/problemset/problem/191/A
题意：
给出 $n$ 个小写字母组成的字符串，两个字符串如果前者的最后一个字母与后者的首字母相同，那么两者可以连接，
同时要求最后得到的一个长字符串的首尾字母也要相同，求最长的满足要求的字符串的长度是多少。
题解：
这个DP蛮有意思的。
记 $f[x][y]$ 为从第一个字符串到当前字符串，字母 $x$ 到字母 $y$ 的最长字符串的长度。
这样，对于当前的字符串 $s_i$，状态转移可以枚举 $k = a \sim z$，维护 $f[k][y] = \max(f[k][y], f[k][x]+|s_i|)$。
由于枚举字符串是从 $s_1$ 到 $s_n$ 的，所以可以确保组合起来时的顺序是正确的，状态转移也是正确的。
AC代码：
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+10; int n; string s[maxn]; int f[30][30]; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; memset(f,-1,sizeof(f)); for(int i=0;i<=‘z‘-‘a‘;i++) f[i][i]=0; for(int i=1;i<=n;i++) { int x=s[i].front()-‘a‘, y=s[i].back()-‘a‘; for(int k=0;k<=‘z‘-‘a‘;k++) { if(f[k][x]==-1) continue; f[k][y]=max(f[k][y],f[k][x]+(int)s[i].size()); } } int res=0; for(int i=0;i<=‘z‘-‘a‘;i++) res=max(res,f[i][i]); cout<<res<<endl; }
PS.动态规划的题还是要多刷，见识更多的套路，有助于开阔思路。
Codeforces 191A - Dynasty Puzzles - [DP]
原文：https://www.cnblogs.com/dilthey/p/10514148.html