造桥

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

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

接下来有

行，每行一个字符串，每个字符串的长度

。

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

。

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

C++(clang++ 11.0.1) 解法, 执行用时: 27ms, 内存消耗: 760K, 提交时间: 2023-08-11 22:48:37

#include<bits/stdc++.h>
using namespace std;

int main(){
  int T; cin >> T;
  while (T--) {
    int n; cin >> n;
    map<char, int> M;
    while (n--) {
      string s; cin >> s;
      M[s.back()] = max(M[s.back()], M[s[0]]+(int)s.size());
    }
    int best = 0;
    for (auto [k, v]: M) best = max(best, v);
    cout << best << endl;
  }
  
}

Python3 解法, 执行用时: 350ms, 内存消耗: 11904K, 提交时间: 2022-06-26 14:16:35

T = int(input())
for _ in range(T):
    n = int(input())
    s = []
    for i in range(n):
        s.append(input())
    f = [0]*26
    for i in range(n):
        o1 = ord(s[i][0])-97
        o2 = ord(s[i][-1])-97
        f[o2] = max(f[o2],f[o1]+len(s[i]))
    print(max(f))

详情