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

· · 题解

前言

本蒟蒻的第一个题解，可能有很多表达不清晰和错误，请谅解

当时在考场没想过会有这么简单的题

思路

不难看出,这是一道DP

我们要遍历一遍字符串

在过程中考虑的无非就是当前遍历字母能不能和前字母组合,再判断哪一个组合分数更高

状态转移方程即为: :::align{center}

dp_i = \max( \operatorname{dp_i} ,\operatorname{dp_{i - 组合字符串长度 }} + \text{对应字符串长度的分数} )

::: 注意:

若此前在遍历字符串的时候遍历到了重复的字符,就要把终止条件改为重复字母的索引,并结束遍历.不然后面的字母会错误的检测字母,从而出现不符合题目要求的字串,导致WA

AC Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string zhun;
    cin >> n >> zhun;
    int shu[n];//其实理论上讲26个位就已经够了，字母表就26个，不可能超过长度为26的符合题意的字串，再长必重复
    for(int i = 1;i<=n;i++)
    {
        cin >> shu[i];
    }
    int end_ = 0;//终止条件
    vector<long long> dp(n+1,0);
    for(int i = 1;i<=n;i++)
    {
        dp[i] = dp[i-1]+shu[1];//先计算长度为1时的分数
        int len = 2;//字串长度,二起步
        for(int j = i-2;j >= end_;j--)
        {
            if(zhun[j] != zhun[i-1])
            {
                dp[i] = max(dp[i],dp[i-len]+shu[len]);//状态转移
            }
            else{
                end_ = j+1;//更改终止条件
                //不必加break,上一个代码等价与break
            }
            len++;//增加字串长度
        }
    }
    cout << dp[n];//输出
}

管理员求过