Dynasty Puzzles

题面翻译

题目描述

有一个王朝，他们国王的名字用姓氏的简写来标记每一代。为了保证王朝的稳定，现在这个王朝的继承人的名字需要满足继承者名字的第一个字母要和前代名字最后一个字母相同。然后拼接起来的名字，第一个字母和最后一个字母相同。现在有一个考古博士，知道了这个王朝国王和亲戚的名字。问你这个王朝所能够得到的最长字符串。

输入

第一行一个整数n(1≤n≤5·1e5),接下来n行，每行一个非空字符串，全由小写字母组成，字符串长度不超过10

输出

最长满足要求的长度，如果没有输出0

构成的字符串必须按输入顺序首尾相接，不能乱序拼接。

分析

理解：给定一些字符串，希望找到最多的字符串，使得他们按照给出的顺序收尾拼接成一个字符串，需要保证最后的字符串首尾相同。

考虑到字符串的拼接一定要按照给出的顺序，即第 $i$ 个字符串一定要接在第 $j$ 个 $(1 ≤ j ＜ i)$ 字符串后面，满足了无后效性（是吗？），这启发我们可以dp解决这个问题。

不妨假设 $f[a][b]$ 表示以字符 $a$ 开头， 字符 $b$ 结尾的最长长度。
最后的答案即为 $\max_{ch = a}^z f[ch][ch]$ （可以这样用吗？）。

按照输入的顺序，枚举当前字符串可以接到哪一个字符结尾的后面，如果当前字符串能接的话就加上自己的长度。

不要忘记每个字符串都要单独更新不拼接任何字符串时的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int n, ans;
int f[30][30];

signed main(){

    cin >> n;
    
    for (string s; n--; ){
        cin >> s; 
        
        int len = s.size();
        int beg = s.front() - 'a';
        int ed = s.back() - 'a';
        
        for (int i = 0; i < 26; i++){
            if (f[i][beg])
                f[i][ed] = max(f[i][ed], len + f[i][beg]);
        }
        
        f[beg][ed] = max(f[beg][ed], len);
        
    }
    
    for (int i = 0; i < 26; i++)
        ans = max(ans, f[i][i]);
    
    cout << ans;
    
    return 0;
}

Written with StackEdit中文版.