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

The_Seas_Tears · 2025-09-28 22:33:21 · 题解

前传

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

思路

根据题目中给出的“价值之和的最大值”，我们可以判断这是一个动态规划；题目中给出了关键信息 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)。

代码实现步骤

1. 读入 n，字符串 s，数组 a；
2. 初始化 dp 数组，大小为 n+1，dp_0=0；

3. 对于 i 从 1 到 n：

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

4. 输出 dp_n。

   代码

   #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;//好习惯
   }