1 条题解

  • 1
    @ 2025-12-9 15:05:05
    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){
        int n,m;
        cin >> n;  // 读入计分序列长度
        vector<int> a(n + 1);  // 计分序列,a[k]表示连续k个abc的得分
        for(int i = 1;i <= n;i++){
            cin >> a[i];  // 读入计分序列
        }
        cin >> m;  // 读入字符串长度
        string s;
        cin >> s;  // 读入字符串
        // dp[i]表示前i个字符能获得的最大得分
        vector<long long> dp(m + 1,0);
        for(int i = 0;i < m;i++){
            // 不选取当前字符作为计分子串的开头,直接继承前一个状态
            dp[i + 1] = max(dp[i + 1],dp[i]);
            // 检查从位置i开始是否是"abc"
            if(i + 2 < m && s.substr(i,3) == "abc"){
                // 选取1个"abc",得分a[1]
                dp[i + 3] = max(dp[i + 3],dp[i] + a[1]);
                // 尝试选取连续多个"abc"
                int k = 1;  // 当前已经匹配的"abc"个数
                // 检查是否能继续匹配更多"abc"
                while(k < n && i + 3 * (k + 1) <= m && s.substr(i + 3 * k,3) == "abc"){
                    k++;  // 增加匹配的"abc"个数
                    // 更新dp值,选取k个连续的"abc",得分a[k]
                    dp[i + 3 * k] = max(dp[i + 3 * k],dp[i] + a[k]);
                }
            }
        }
        // 输出整个字符串的最大得分
        cout << dp[m];
        return 0;
    }
    
    • 1

    信息

    ID
    779
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度暂无评定
    标签
    递交数
    1
    已通过
    1
    上传者