题目描述

小杨想要计算由 $m$ 个小写字母组成的字符串的得分。

小杨设置了一个包含 $n$ 个正整数的计分序列 $A=[a_1,a_2,\dots ,a_n]$，如果字符串的一个子串由 $k(1\le k\le n)$ 个 $\text{abc}$ 首尾相接组成，那么能够得到分数 $a_k$，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

例如，假设 ，字符串 $\text{dabcabcabcabzabc}$ 的所有可能计分方式如下：

• $\text{d+abc+abcabc+abz+abc}$ 或者 $\text{d+abcabc+abc+abz+abc}$，其中 $\text{d}$ 和 $\text{abz}$ 不计算得分，总得分为 $a_1+a_2+a_1$。
• $\text{d+abc+abc+abc+abz+abc}$，总得分为 $a_1+a_1+a_1+a_1$。
• $\text{d+abcabcabc+abz+abc}$，总得分为 $a_3+a_1$。

小杨想知道对于给定的字符串，最大总得分是多少。

输入格式

• 第一行包含一个正整数 $n$，代表计分序列 $A$ 的长度。

• 第二行包含 $n$ 个正整数，代表计分序列 $A$。

• 第三行包含一个正整数 $m$，代表字符串的长度。

• 第四行包含一个由 $m$ 个小写字母组成的字符串。

输出格式

输出一个整数，代表给定字符串的最大总得分。

输入输出样例 #1

输入 #1

3
3 1 2
13
dabcabcabcabz

输出 #1

9

说明/提示

样例解释

最优的计分方式为 $\text{d+abc+abc+abc+abz}$，总得分为 $a_1+a_1+a_1$，共 $9$ 分。

数据范围

对于全部数据，保证有 $1\le n\le 20$，$1\le m\le 10^5$，$1\le a_i\le 1000$。

2 solution

先统计连续的 abc 个数，并用动态规划算出最优得分

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"

using namespace std;

int n, m, a[21];
string s;

int main() {

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cin >> m >> s;

    vector<int> b;
    int x = 0, M = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s.substr(i, 3) == "abc") {
            x++;
            i += 2;
        } else {
            if (x) b.push_back(x), M = max(M, x);
            x = 0;
        }
    }

    if (x) b.push_back(x);

    vector<int> f(M + 1);

    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= min(i, n); j++) {
            f[i] = max(f[i], f[i - j] + a[j]);
        }
    }


    int sum = 0;
    for(int i : b) sum += f[i];
    cout << sum;

}

结果