题目描述

难度分:$1500$

输入$n(1 \leq n \leq 5 \times 10^5)$和长为$n$的字符串数组$a$，只包含小写字母，每个$a[i]$的长度至多为$10$。

你需要选择$a$的一个子序列$b$，满足$b[i]$的最后一个字母等于$b[i+1]$的第一个字母，且$b[1]$的第一个字母等于 $b[-1]$的最后一个字母。这里$b[-1]$表示最后一项。

输出$b$中字符串长度之和的最大值。

注：子序列不要求连续。

输入样例$1$

3
abc
ca
cba

输出样例$1$

6

输入样例$2$

4
vvp
vvp
dam
vvp

输出样例$2$

0

输入样例$3$

3
ab
c
def

输出样例$3$

1

算法

动态规划

状态定义

$f[i][last][head]$表示已经考虑完子数组$[1,i)$，上一个字母为$last$，当前选出来的$b$序列的首字母为$head$的情况下，子数组$[i,n]$能够为答案贡献的最大长度。按照这种状态定义方法，显然答案就是$max_{letter=a}^{z}f[1][letter][letter]$。

状态转移

$base$ $case$：当$i \gt n$时，只要$last=head$（且$last$是切实有效的字母），说明最后一个字符串与第一个字符串形成了闭环，可以返回$0$，不然就是个无效解，返回负无穷。

一般情况：当前字符串是可以直接跳过的，状态转移方程为

$f[i][last][head]=f[i+1][last][head]$

如果不跳过，分为两种情况

1. $a[i]$需要作为$b[1]$，此时状态转移方程为$f[i][last][head]=f[i+1][a[i][len]][a[i][1]]+len$（其中$len$是$a[i]$的长度）。
2. $a[i]$不是$b$序列的第一个字符串，此时必须要$a[i][1]=last$才能进行状态转移，状态转移方程为$f[i][last][head]=f[i+1][a[i][len]][head]+len$。

以上两种情况选较大值转移即可，先给出一种记忆化搜索的写法，然后再通过分析复杂度来优化。

记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 500001;
int n;
char words[N][15];
int f[N][27][27];

int dfs(int i, int last, int head) {
    int &v = f[i][last][head];
    if(v != -1) return v;
    if(i > n) {
        if(last == 0) return v = -0x3f3f3f3f;
        if(last == head) {
            return v = 0;
        }else {
            return v = -0x3f3f3f3f;
        }
    }
    int len = strlen(words[i] + 1);
    if(last == 0) {
        int t = words[i][len] - 'a' + 1;
        int h = words[i][1] - 'a' + 1;
        return v = max(dfs(i + 1, last, head), len + dfs(i + 1, t, h));
    }else {
        int res = dfs(i + 1, last, head);
        if(words[i][1] - 'a' + 1 == last) {
            res = max(res, len + dfs(i + 1, words[i][len] - 'a' + 1, head));
        }
        return v = res;
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%s", words[i] + 1);
    }
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(1, 0, 0));
    return 0;
}

复杂度分析

时间复杂度

状态数量为$\Sigma^2 n$，其中$\Sigma$为字符集的大小，单次转移的时间复杂度为$O(1)$，因此算法的时间复杂度为$O(\Sigma^2n)$。

空间复杂度

如果按照这个状态的定义来做，存储$\Sigma^2n$个状态是会超空间的，因此至少不能用记忆化搜索来实现这个算法。而我们从记忆化搜索的代码上注意到，$f[i]$的状态仅依赖于$f[i+1]$的状态，因此可以用滚动数组来进行空间的优化（记忆化搜索必须改成迭代的DP写法），将$f_{n \times \Sigma \times \Sigma}$的DP矩阵的第一维优化掉，变成$\Sigma^2$规模的。如果不算输入的字符串数组$a$，那么额外空间复杂度就是$O(\Sigma^2)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 500001;
int n;
char words[N][15];
int f[27][27];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%s", words[i] + 1);
    }
    memset(f, -0x3f, sizeof(f));
    for(int i = 1; i <= 26; i++) {
        f[i][i] = 0;
    }
    for(int i = n; i >= 1; i--) {
        int len = strlen(words[i] + 1);
        for(int last = 0; last <= 26; last++) {
            for(int head = 0; head <= 26; head++) {
                if(last == 0 && head > 0) break;
                int t = words[i][len] - 'a' + 1;
                int h = words[i][1] - 'a' + 1;
                if(last == 0) {
                    f[last][head] = max(f[t][h] + len, f[last][head]);
                }else {
                    if(words[i][1] - 'a' + 1 == last) {
                        f[last][head] = max(f[last][head], len + f[t][head]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= 26; i++) {
        ans = max(ans, f[i][i]);
    }
    printf("%d\n", ans);
    return 0;
}