题解：P12124 [蓝桥杯 2024 省 B 第二场] 前缀总分

· · 题解

题意简述

给定 n 个字符串 s_{1 \sim n} ，修改某字符串的某个字符，使 \sum_{i<j} \operatorname{LCP}(s_i,s_j) 最大。\operatorname{LCP}(p, q) 为字符串 p, q 的最长公共前缀长度。

思路

考虑 dp。定义 f_{i, j, k} 表示 s_i 和 s_j 从第 k 位开始到结尾的子串的最长公共前缀长度。

状态转移：

f_{i, j, k} = \begin{cases} 0, & s_{i, k} \neq s_{j, k}\\ f_{i, j, k+1} + 1, & s_{i, k} = s_{j, k} \end{cases}

统计答案时，我们枚举要修改的字符串编号 i，修改字符的下标 k 和修改后的字符 c。记这次修改可以使答案增加 d。对于所有 j \neq i，有以下两种情况使答案变动：

记原本不加修改的答案为 ans。则 ans + \max\{d\} 即为最终答案。时间复杂度 \mathcal O(n^2|s_i||\sum|)，其中 |\sum| = 26。

代码

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

const int N = 205;
string s[N];
int f[N][N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = min(s[i].size(), s[j].size())-1; k >= 1; k--)
                if (s[i][k] == s[j][k])
                    f[i][j][k] = f[i][j][k+1] + 1;
    int ans0 = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            ans0 += f[i][j][1];
    int ans = ans0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k < s[i].size(); k++) {
            for (char c = 'a'; c <= 'z'; c++) {
                int add = 0;
                for (int j = 1; j <= n; j++) {
                    if (j == i || k >= s[j].size()) continue;
                    if (f[i][j][1] == k-1 && c == s[j][k])
                        add += f[i][j][k+1]+1;
                    if (f[i][j][1] >= k && c != s[j][k])
                        add -= f[i][j][1]-k+1;
                }
                ans = max(ans, ans0+add);
            }
        }
    }
    cout << ans << endl;
    return 0;
}