蓝桥杯笔记-2023年第十四届省赛真题-松散子序列_蓝桥杯松散子序列c++

题目描述

给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符 对应了原字符串中的第 pi 个字符。我们定义 s 的一个松散子序列为：对于 i > 1 总是有 pi − pi−1 ≥ 2 。设一个子序列的价值为其包含的每个字符的价值之和 ( a ∼ z 分别为 1 ∼ 26 ) 。 

求 s 的松散子序列中的最大价值。 

输入格式

输入一行包含一个字符串 s 。 

输出格式

输出一行包含一个整数表示答案。 

样例输入

azaazaz

样例输出

78

提示

对于 20% 的评测用例，|s| ≤ 10 ； 

对于 40% 的评测用例，|s| ≤ 300 ；

对于 70% 的评测用例，|s| ≤ 5000 ； 

对于所有评测用例，1 ≤ |s| ≤ 106，字符串中仅包含小写字母。

问题重述

有一段字符串，其子序列满足两个字符间距离大于2，找到满足该要求子序列最大字符价值。

问题分析

问题的解由一个个子问题得出，典型的动态规划问题，要找到最大子序列字符价值，我们可以先建立动态规划递推式，现有用例为‘abcdefg’，有如下步骤：

指针指到a时，我们可以看作在字符串为‘a’中找最大价值，显而易见为1(a的价值)。

指针指到b时，不能构成题目要求的子序列，可得到字符串为'ab'时最大价值为2(a<b)。

指针指到c时，由于c-a>=2，字符串'abc'有子序列'ac'，比较与'a','b','c'，可得到最大值为4(a+c)。

指针指到d时，字符串'abcd'有子序列'ac','bd'，最大价值为6(b+d)。

指针指到e时，字符串’abcde‘有子序列’ace‘,'bd','ce'，最大子序列为4(a+c)+5(e)=9，可以看到规律了。

指针指到f时，字符串'abcdef’有子序列'ace','acf','adf','bdf','ce'.....最大子序列为6(b+d)+6(f)=12。

指针指到g时，字符串'abcdefg‘最大价值为max(6(b+d)+g(7)=13,9(a+c+e)+g(7)=16)=16。

由此可以推出关系式：

为方便编写，防止边界问题，将dp列表左边插入3个值为0的列表，由此可避免在遍历s时考虑边界问题。

参考代码

s = input()
dp = [0,0,0]+[ord(s[i])-96 for i in range(len(s))]
for i in range(3,len(s)+3):
    dp[i] += max(dp[i-2],dp[i-3])
print(max(dp[-1],dp[-2]))

运行结果

运行地址https://www.dotcpp.com/oj/problem3181.html