[牛客月赛47] D造桥 字符串拼接问题+动态规划

前言

传送门 :

题意

给定 n n n个字符串,询问拼接的最大长度是多少

解释 : 拼接也就是首位相连,两个字符串只有拼接的地方相同才可以拼接

思路

小数据可以 d f s dfs dfs,大数据就是 d p dp dp模板题了

状态表示 : d p [ i ] dp[i] dp[i]以 i i i结尾的最大长度

状态计算 :

d p [ b ] = m a x ( d p [ b ] , d p [ a ] + s . s i z e ( ) ) dp[b] = max(dp[b],dp[a]+s.size()) dp[b]=max(dp[b],dp[a]+s.size())

最后枚举一下答案即可

Mycode

const int N = 26;
int f[N];
void solve(){
	memset(f,0,sizeof f);
	int n;cin>>n;
	for(int i=1;i>s;
		int a = s[0]-'a',b = s[s.size()-1]-'a';
		f[b] = max(f[b],f[a]+(int)s.size());
	}

	int ans =  0;

	for(int i =0 ; i