造桥

题目描述

今天是愉快的周末，牛可乐和牛妹在一起玩游戏。牛妹给了牛可乐  个造桥的零件，每个零件以字符串的形式给出，每个字符串两端的字符是零件的接口，两个零件可以通过连接不同端的接口（一个零件的左端只能连接另一个零件的右端，右端则只能连接左端）得到一个更长的零件，新零件的长度是原零件的长度之和。

牛妹规定，零件不能翻转，且零件左边的接口只能由该零件左边的零件去连接（这意味着，应该按顺序选取零件），右端同理。

牛可乐想得到牛妹的赞许，因此他要想用牛妹给的零件拼接一个尽可能长的桥梁，你能帮帮他吗？

输入描述:

	

		第一行一个整数  ，代表案例数。
	

	

		对于每一个案例：第一行一个数  ，表示字符串的个数。
	

	

		    接下来有  行，每行一个字符串，每个字符串的长度  。
	

	

		
	

	

		所有案例的字符串长度的和不超过 。
	

	

		保证所有字符均为小写字符。
	

输出描述:

	

		  个字符串能拼接的最大字符串长度。
	

示例1

输入

复制 1 6 ab baabc bb ba ba ad

1
6
ab
baabc
bb
ba
ba
ad

输出

复制 8

8

说明

按顺序依次拼接：1，3，5，6号字符串。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a;i<=b;++i)
#define per(i,a,b) for (int i=a;i>=b;--i)
typedef long long ll;
const long long mod = 1e9+7;
const int N = 2e5+5;

int n;
int dp[30];
int main() {     
	int t; cin >> t;
	while (t--) {
		memset(dp,0,sizeof(dp));
		scanf("%d",&n);
		rep(i,1,n) {
			string s;
			cin >> s;
			int a = s[0] - 'a', b = s[s.length()-1] - 'a';
			dp[b] = max(dp[b],int(dp[a] + s.length()));
		}
		int maxx = 0;
		rep(i,0,25) maxx = max(maxx,dp[i]);
		cout << maxx << endl;
	}
	return 0;
}