题目描述

Narek 有 $n$ 个字符串，每个字符串长度为 $m$。他可以选择其中一些字符串（保持原顺序）拼接起来，然后扫描这个拼接后的字符串：

• 他按顺序寻找 "n" → "a" → "r" → "e" → "k"，找到完整的一组（$5$ 个字母），他的得分 $\text{score}_n$ 增加 $5$，然后从头开始找下一组。
• 在扫描过程中，如果他遇到 "n"、"a"、"r"、"e"、"k" 中但不是当前要找的下一个字母，则 ChatGPT 的得分 $\text{score}_c$ 增加 $1$。
• 如果最后一组没完成（比如只找到了 "n"、"a"、"r" 三个字母就结束了），则这些已找到的字母也计入 $\text{score}_c$，而 Narek 不得分。

定义：

目标：选择一个子序列（可空），使得差值最大。

解题思路

关键观察

1. 不能贪心：因为一个字符串的结尾可能帮助下一个字符串的开头继续匹配。
2. 状态表示：我们只关心当前匹配到 "narek" 的第几个字母，用 $0 \sim 4$ 表示：
   • $0$：正在找 'n'
   • $1$：正在找 'a'
   • $2$：正在找 'r'
   • $3$：正在找 'e'
   • $4$：正在找 'k'
3. 一次完整匹配：当状态 $4$ 且当前字符是 'k'，则完成一组，状态回到 $0$，Narek 得 $5$ 分。

动态规划设计

设 $dp[j]$ 表示：当前匹配进度为 $j$ 时，已经得到的最大差值（$\text{score}_n - \text{score}_c$）。

初始：

我们逐个处理每个字符串。对于当前字符串 $s$：

如果不选它，$dp$ 不变。 如果选它，我们从每个可能的进度 $j$ 出发，模拟扫描 $s$，计算： 新的进度 $next$ 差值变化 $delta$

然后更新：

其中 $dp'$ 是处理完当前字符串后的新 DP 数组。

差值变化 $delta$ 的计算

扫描 $s$ 的每个字符 $ch$：

如果 $ch$ 不在 "narek" 中，忽略。 找到 $ch$ 在 "narek" 中的位置 $ind$（$0$ 表示 'n'，$1$ 表示 'a'，依此类推）。 如果 $ind == next$（即正好是我们要找的下一个字母）： 匹配成功，$next = (next + 1) \% 5$ 如果 $next$ 变成 $0$（说明完成一组），则 Narek 得 $5$ 分，体现在 $delta$ 中（我们稍后用 $delta$ 累加）。 为了方便，标程里每匹配一个字母就 $delta$ 加 $1$（表示 Narek 得 $1$ 分，但注意一组是 $5$ 分，这样最后 $delta$ 就是 $5$ 分）。 否则（$ind \neq next$）： 这个字母是 "narek" 中的字母，但不是当前要找的，ChatGPT 得 $1$ 分，所以 $delta$ 减 $1$。

实际上，标程用一个 counted_score 变量累加：

• 匹配正确字母：counted_score++
• 匹配错误（属于 "narek" 但不是当前要找的）：counted_score--

这样处理完一个字符串后，counted_score 就是选这个字符串带来的差值变化。

为什么要用两个 DP 数组？

因为一个字符串只能选一次，我们不能在同一个字符串的循环中重复使用更新后的状态。
所以用 $dp$ 表示上一轮结束后的状态，$ndp$ 初始等于 $dp$（表示不选当前串），然后在 $dp$ 的基础上更新 $ndp$。

最后答案

处理完所有字符串后，对于每个进度 $i$：

• 如果 $i = 0$，说明最后一组完整结束，差值直接就是 $dp[0]$。
• 如果 $i > 0$，说明最后一组没完成，有 $i$ 个字母被 Narek 匹配了但没完成一组。
  根据规则，这些字母应该给 ChatGPT 加分，同时 Narek 不得这组的分。
  所以实际差值要减去 $2i$（$i$ 分从 Narek 扣除，$i$ 分给 ChatGPT 增加）。

因此：

完整代码（带注释）

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

const string narek = "narek";  // 目标字母序列

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

    int t; cin >> t;  // 测试用例数

    while (t--) {
        int n, m; cin >> n >> m;
        vector<string> s(n);
        for (int i = 0; i < n; i++) {
            cin >> s[i];
        }

        // dp[j]：当前进度为 j 时的最大差值
        // 初始：进度 0 得 0 分，其他进度不可能
        vector<int> dp(5, -1e9);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            vector<int> ndp = dp;  // 不选当前字符串的情况

            for (int j = 0; j < 5; j++) {
                if (dp[j] == -1e9) continue;  // 无法到达的状态

                int cnt = 0;      // 差值变化
                int nxt = j;      // 新进度

                // 扫描当前字符串
                for (char ch : s[i]) {
                    int pos = narek.find(ch);
                    if (pos == string::npos) continue;  // 不是 n/a/r/e/k 的字母忽略

                    if (pos == nxt) {  // 正好是下一个要找的字母
                        nxt = (nxt + 1) % 5;
                        cnt++;        // 匹配正确，Narek 得 1 分
                    } else {
                        cnt--;        // 匹配错误（属于目标字母但不是当前要的），ChatGPT 得 1 分
                    }
                }

                // 更新 ndp
                ndp[nxt] = max(ndp[nxt], dp[j] + cnt);
            }

            dp = ndp;  // 更新 dp
        }

        int ans = 0;
        for (int i = 0; i < 5; i++) {
            ans = max(ans, dp[i] - 2 * i);  // 处理未完成的一组
        }
        cout << ans << "\n";
    }

    return 0;
}

复杂度分析

• 对于每个字符串，我们枚举 $5$ 种进度 $j$。
• 对每种进度，扫描字符串的 $m$ 个字符。
• 总复杂度 $O(n \cdot m \cdot 5)$。
• 题目保证所有测试用例的 $n \cdot m$ 总和 $\le 10^6$，因此完全可行。