d p i , j dp_{i,j} dpi,j 表示以 i i i 开始以 j j j 结尾的最长长度。
方程: d p j , r = m a x ( d p j , l , d p j , l + l e n g t h l , r ) dp_{j,r}=max(dp_{j,l}\;,\;dp_{j,l}+length_{l,r}) dpj,r=max(dpj,l,dpj,l+lengthl,r) 有点区间 d p dp dp 的意思。枚举 j j j ,断点取 l l l 。
signedmain(){
int T =1;// T = read();while(T--){
int n =read();
vector<tuple<int,int,int>>s(n +1);for(int i =1; i <= n;++i){
string t; cin >> t;int a = t[0]-'a', b = t.size()^1? t[t.size()-1]-'a': a, c = t.size();
s[i]={
a, b, c};}
vector<vector<int>>dp(26,vector<int>(26));for(int i =1; i <= n;++i){
auto[l, r, len]= s[i];for(int j =0; j <26;++j){
if(dp[j][l]) dp[j][r]=max(dp[j][r], dp[j][l]+ len);}
dp[l][r]=max(dp[l][r], len);}int ans =0;for(int i =0; i <26;++i) ans =max(ans, dp[i][i]);write(ans);}return0;}