12848.划分字符串

好的，我们来详细分析这道字符串划分的题目。以下是符合要求的题解。

---

题目分析

我们有一个长度为 $n$ 的字符串 $s$，需要将它划分成多个连续子串。
限制条件：每个子串内的字母互不相同（每个字母至多出现一次）。
价值条件：长度为 $len$ 的子串会获得价值 $a_{len}$。
目标：通过划分使得所有子串的价值总和最大。

示例：s = "street", a = [1,2,3,4,5,6]（实际价值由输入决定）
一种合法划分是 str + e + e + t，对应的价值和为 $a_3 + a_1 + a_1 + a_1$。
像 s + tree + t 是非法的，因为 tree 中 e 出现了两次。

题目要求我们求出最大的总价值。

解题思路

这是一道典型的动态规划问题。

设 f[i] 表示考虑字符串前 $i$ 个字符时，能够获得的最大价值总和。
最终答案即为 f[n]。

状态转移：
我们要找到最后一段子串 s[j...i]（$1 \le j \le i$），这段子串满足“所有字母互不相同”，那么有：

f[i] = max{ f[j-1] + a[i - j + 1] }   (其中 s[j...i] 内无重复字母)

如果暴力枚举所有可能的 $j$，复杂度是 $O(n^2)$ 的。对于 $n \le 10^5$ 会超时。
但我们有一个关键的性质：字符串只由小写字母组成，总的字符种类只有 $26$ 种。
因此，任何一个“无重复字母”的子串，其长度不可能超过 $26$（字母只有 $26$ 个，第 $27$ 个字母必然会重复）。

利用这一点，我们可以对每个 $i$，只向左检查最多 $26$ 个位置，一旦遇到重复字母就停止。这样单次转移的复杂度降为 $O(26)$，总复杂度 $O(26n) = O(n)$，可以完美通过 $10^5$ 的数据。

算法说明

1. 读入 $n$、字符串 $s$（下标从 $1$ 开始存储方便处理）和价值数组 $a[1..n]$。
2. 定义 f[0] = 0，f[i] 初始设为 $0$ 或极小值。
3. 对于每个 $i$ 从 $1$ 到 $n$：
   • 用一个整数 mask 来记录当前子串中已经出现过的字母集合（二进制第 $k$ 位表示第 $k$ 个字母是否出现过）。
   • $j$ 从 $i$ 开始向左扫描到 $1$：
     • 设当前字符 s[j] 对应字母编号 cur = 1 << (s[j] - 'a')。
     • 如果 mask & cur != 0，说明 s[j] 已经在子串 s[j...i] 中出现过，不能再向左扩展，直接跳出循环。
     • 否则，将 cur 加入 mask：mask |= cur。
     • 此时 s[j...i] 是合法子串，长度为 len = i - j + 1。
     • 尝试用 f[j-1] + a[len] 更新 f[i]（取较大值）。
4. 最后输出 f[n] 即可。

为何不需要特别处理长度超过 $n$ 的 $a$ 值？
因为子串长度不会超过 $i$ 也不会超过总长度 $n$，价值数组下标保证在 $1\sim n$ 内。

时间复杂度分析

对于每个 $i$，内层循环最多执行 $26$ 次（mask 最多右移加入 $26$ 种不同字母，之后必然重复并跳出）。
总循环次数约为 $n \times 26$。
当 $n = 10^5$ 时，运算量约为 $2.6 \times 10^6$，完全满足 $1000$ms 的时间限制。

空间复杂度：$O(n)$，用于存储字符串、价值数组和 DP 数组。

参考代码（附解释）

cpp
复制
1#include <algorithm>
2#include <cstdio>
3#include <vector>
4using namespace std;
5
6const int N = 1e5 + 5;
7int n;
8char s[N];
9int a[N];
10long long f[N];          // 注意价值可能很大，要用 long long
11
12int main() {
13    scanf("%d", &n);
14    scanf("%s", s + 1);  // 下标从 1 开始
15    for (int i = 1; i <= n; i++) 
16        scanf("%d", &a[i]);
17
18    // 动态规划
19    for (int i = 1; i <= n; i++) {
20        int mask = 0;    // 记录当前扫描到的字母集合
21        // 向左扩展子串 s[j...i]
22        for (int j = i; j >= 1; j--) {
23            int cur = 1 << (s[j] - 'a'); // 当前字母对应的二进制位
24            if (mask & cur) 
25                break;                   // 字母重复，停止扩展
26            mask |= cur;                 // 将字母加入集合
27            int len = i - j + 1;
28            f[i] = max(f[i], f[j - 1] + a[len]); // 更新最大值
29        }
30    }
31
32    printf("%lld\n", f[n]);
33    return 0;
34}

代码要点解释：

• 使用 mask 记录字母是否出现，是 OI 中处理小写字母去重的常用技巧，避免了每次判断都扫描整个子串。
• 内层循环检测到重复（mask & cur != 0）立即 break，保证了复杂度被严格限制在 $26$ 以内。
• f[j-1] + a[len] 包含了将前 $j-1$ 个字符划分的最优解，加上当前这段合法子串的价值，不断取优。
• 由于 $a_i$ 最大到 $10^9$，累加可能超出 int，所以 f 数组使用 long long 类型。

总结

本题巧妙结合了动态规划和字符串去重的性质。利用“无重复字母子串长度不超过字符集大小”这一事实，将看似 $O(n^2)$ 的 DP 优化至 $O(n \times \Sigma)$（$\Sigma$ 为字符集大小，这里是 $26$），从而轻松应对 $n=10^5$ 的数据规模。这类“看似暴力实则线性”的思路在字符串 DP 中非常值得学习。