题目传送门:D-造桥_牛客小白月赛47 (nowcoder.com)
题目大意请看原题。
思路
每一个零件相当于一条边,边权为字符串长度,起点是第一个字符,终点为最后一个字符。
我们用dp[i]表示以字符i结尾所能得到的最长的桥的长度,那么就有状态转移方程:

全部更新完成之后,从dp['a'] ~ dp['z']中选出最大输出的即可。
代码
/*Copyright (C) Eriktse 2022*/ #include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 10; int dp['z' + 1]; void solve() { memset(dp, 0, sizeof dp); int N;cin >> N; for(int i = 1;i <= N; ++ i) { string s;cin >> s; dp[s.back()] = max(dp[s.back()], (int)s.size() + dp[s.front()]); } int ans = 0; for(char ch = 'a';ch <= 'z'; ++ ch)ans = max(ans, dp[ch]); cout << ans << '\n'; } signed main() { int T;cin >> T; while(T --)solve(); return 0; }
Comments NOTHING