前传

六级考生一枚，考场上没调出来，准备下一次了。结果发现推导公式推错了。

思路

根据题目中给出的“价值之和的最大值”，我们可以判断这是一个动态规划；题目中给出了关键信息

a_i

，代表的是把字串划分为

i

长度可以得到

a_i

分。

$dp$ 数组的定义

我们定义

dp_i

为前

i

个字符（即

s_0

到

s_i

）的最大价值之和。

$dp$ 数组的状态转移方程

对于每个位置

i

（从

1

到

n

），我们尝试从

j

（从

i-1

到

0

）往回看，看字串

s_j

到

s_i

是否满足每个字符只出现一次。那么

dp_i=\max(dp_i,dp_j+a_{i-j-1})

。

注意

如果

a

数组下标从

0

开始，所以长度为

l

的字串价值为

a_{l-1}

。

但是，直接这样做最坏情况下时间复杂度为

O(n^2)

，可能会超时。

优化思路

由于字符串只包含小写字母，最多

26

种字符，所以当我们从

i-1

往回遍历时，如果遇到重复字符就可以提前退出循环，我们用一个集合来记录当前字串的字符。

这样，我们最多检查

26

次，时间复杂度为

O(26 \times n)

，可以记为

O(n)

。

代码实现步骤

读入 $n$ ，字符串 $s$ ，数组 $a$ ；
初始化 $dp$ 数组，大小为 $n+1$ ， $dp_0=0$ ；
对于 $i$ 从 $1$ 到 $n$ ：

初始化集合为 $0$ ，从 $i-1$ 开始一直循环到 $0$ ，如果这个字符已经在集合里了，就退出循环，否则将 $s_j$ 加入集合，继续更新 $dp$ 数组。
输出 $dp_n$ 。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n;
string s;
long long a[N],dp[N];//防止溢出
int mp[120];
int main(){
    ios::sync_with_stdio(0);//加速输入输出速度
    cin.tie(0),cout.tie(0);
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        unordered_set<char> st;
        for(int j=i-1;j>=0;j--){
            if(st.find(s[j])!=st.end())break;//如果该字串中存在该字符了，就退出循环
            st.insert(s[j]);//否则就加入新的
            dp[i]=max(dp[i],dp[j]+a[i-j-1]);//推导公式
        }
    }
    cout<<dp[n];
    return 0;//好习惯
}

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

文章操作

前传

思路

$dp$ 数组的定义

$dp$ 数组的状态转移方程

注意

优化思路

代码实现步骤

代码

相关推荐

评论

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

文章操作

前传

思路

dpdpdp 数组的定义

dpdpdp 数组的状态转移方程

注意

优化思路

代码实现步骤

代码

相关推荐

评论

$dp$ 数组的定义

$dp$ 数组的状态转移方程