专栏文章

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

zzhonggong
P14075题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@minree1j
此快照首次捕获于
2025/12/02 07:07
3 个月前
此快照最后确认于
2025/12/02 07:07
3 个月前
查看原文
题目传送门。
题目说我们要给字符串分段，所以我们可以从长度为 11 的字符串开始，一步一步推导，求出最后字符串的最大价值。

代码：

CPP
#include <iostream>
#include <cstring>
using namespace std;
long long a[100001],dp[100001];
bool u[200];
int main()
{
    int n;
    string s;
    cin>>n>>s;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=min(i,30);++j)
        {
            if(u[s[i-j]]==1) break;
            dp[i]=max(dp[i],dp[i-j]+a[j]);
            u[s[i-j]]=1;
        }
        if(dp[i]==0) dp[i]=a[i];
        for(int i='a';i<='z';++i)
            u[i]=0;
    }
    cout<<dp[n];
    return 0;
}
蒟蒻的第一篇题解，求过。

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...