P14075 [GESP202509 六级] 划分字符串

题目描述

小 A 有一个由 $n$ 个小写字母组成的字符串 $s$。他希望将 $s$ 划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串 street 来说，str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串 tree 中 e 出现了两次。

额外地，小 A 还给出了价值 $a_1,a_2,\dots ,a_n$，表示划分后长度为 $i$ 的子串价值为 $a_i$。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？

输入格式

第一行，一个正整数 $n$，表示字符串的长度。

第二行，一个包含 $n$ 个小写字母的字符串 $s$。

第三行，$n$ 个正整数 $a_1,a_2,\dots ,a_n$，表示不同长度的子串价值。

输出格式

一行，一个整数，表示划分后子串价值之和的最大值。

输入输出样例 #1

输入 #1

6
street
2 1 7 4 3 3

输出 #1

13

输入输出样例 #2

输入 #2

8
blossoms
1 1 2 3 5 8 13 21

输出 #2

8

说明/提示

对于 $40\%$ 的测试点，保证 $1\le n\le 10^3$。

对于所有测试点，保证 $1\le n\le 10^5$，$1\le a_i\le 10^9$。

解析

动态规划，详见代码：

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

int n;
string s;
long long dp[100005]; // dp[i] 表示前 i 个字符划分后的最大总价值
int a[100005];
bool b[26]; // 标记字母是否出现过
int main() {
    cin >> n;
    cin >> s;
    s = ' ' + s; // 调整下标从 1 到 n，方便处理
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 初始化 dp[0] = 0（前 0 个字符价值为 0）
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        memset(b, 0, sizeof(b)); // 重置字母出现标记
        for (int j = i; j >= 1; j--) {
            // 检查 s[j] 是否已经在当前段出现过
            if (b[s[j] - 'a'] == 1) {
                // 出现重复，不能再往左扩展
                break;
            }
            // 标记当前字母已出现
            b[s[j] - 'a'] = 1;
            // 当前段为 s[j..i]，长度 len = i - j + 1
            // 价值为 a[len]
            dp[i] = max(dp[i], dp[j - 1] + a[i - j + 1]);
        }
    }
    cout << dp[n];
    return 0;
}