Codefroces 191A - Dynasty Puzzles

思路

• $dp$
• $d{p}_{i,j}$ 表示以 $i$ 开始以 $j$ 结尾的最长长度。
• 方程：$d{p}_{j,r}=max(d{p}_{j,l},d{p}_{j,l}+lengt{h}_{l,r})$ 有点区间 $dp$ 的意思。枚举 $j$ ，断点取 $l$ 。

signed main() {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);}return 0;
}