G6007 [GESP202406 六级] 计算得分 题解

知识点：完全背包、字符串分段、动态规划。

解题思路

先用完全背包式DP求连续r个abc块的最高分，dp[r]=max(dp[r-k]+a[k])。扫描字符串划出连续abc块段，逐段累加其dp值。

为什么正确

不完整的abc会隔断可计分子串，不同连续段独立；段内按最后一组块数分解，DP穷尽所有不重叠划分。

易错点

匹配abc后下标前进3，失配时前进1并结算当前段；末尾一段需额外结算。

复杂度

时间O(nm)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    string s;
    cin>>s;
    vector<long long>dp(m/3+1);
    for(int i=1;i<(int)dp.size();i++)for(int k=1;k<=n&&k<=i;k++)dp[i]=max(dp[i],dp[i-k]+a[k]);
    long long ans=0;
    int run=0;
    for(int i=0;i<m;) {
        if(i+2<m&&s.substr(i,3)=="abc") {
            run++;
            i+=3;
        }
        else {
            ans+=dp[run];
            run=0;
            i++;
        }
    }
    cout<<ans+dp[run];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。