G6017 [GESP202509 六级] 划分字符串 题解

知识点：动态规划、位运算、字符串。

解题思路

令dp[i]为前i个字符的最高分。从i往左枚举最后一段，用26位掩码记录出现字母，遇重复立即停止，合法段按长度收益转移。

为什么正确

最后一段不能有重复字符，因此最长26；枚举所有合法后缀并接前缀最优解覆盖全部划分。

易错点

遇重复后更长段也必非法，可直接break；位掩码每个右端重新清空。

复杂度

时间O(26n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin>>n>>s;
    vector<long long>a(n+1),dp(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++) {
        int mask=0;
        for(int j=i-1;j>=0&&i-j<=26;j--) {
            int bit=1<<(s[j]-'a');
            if(mask&bit)break;
            mask|=bit;
            dp[i]=max(dp[i],dp[j]+a[i-j]);
        }
    }
    cout<<dp[n];
}

说明

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