Code blocks，Codeforces Round #121 (Div. 1) A. Dynasty Puzzles DP

2023-11-19 阅读 25 评论 0

摘要：鏈接： http://codeforces.com/contest/191/problem/A 題意：給出n個字符串，兩個字符串如果前一個的尾與后一個的首相同，那么可以相連，最后得到的字符串要滿足首尾相同，問最長的符合要求的字符串的長度是多少。字符串必須按給出順序

鏈接：

http://codeforces.com/contest/191/problem/A

題意：

給出n個字符串，兩個字符串如果前一個的尾與后一個的首相同，那么可以相連，最后得到的字符串要滿足首尾相同，問最長的符合要求的字符串的長度是多少。

字符串必須按給出順序相連

題解：

定義狀態dp[i][j]代表以i開頭以j結尾的最長的字符串的長度

開始的時候我45行寫成了!dp[u][v]，貢獻了一次wa

代碼：

31 int dp[26][26];
32 
33 int main() {
34     ios::sync_with_stdio(false), cin.tie(0);
35     int n;
36     cin >> n;
37     rep(i, 0, n) {
38         string s;
39         cin >> s;
40         int len = s.length();
41         int u = s[0] - 'a';
42         int v = s[len - 1] - 'a';
43         rep(i, 0, 26) if (dp[i][u])
44             dp[i][v] = max(dp[i][v], dp[i][u] + len);
45         if (len > dp[u][v]) dp[u][v] = len;
46     }
47     int ans = 0;
48     rep(i, 0, 26) ans = max(ans, dp[i][i]);
49     cout << ans << endl;
50     return 0;
51 }