松散子序列（第十四届蓝桥杯省赛PythonB组）_松散子序列python

给定一个仅含小写字母的字符串 s，假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi 个字符。

我们定义 s 的一个松散子序列为：对于 i>1 总是有 pi−pi−1≥2。

设一个子序列的价值为其包含的每个字符的价值之和（a∼z 分别为 1∼26）。

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

输入格式

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

输出格式

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

数据范围

对于 20%的评测用例，|s|≤10；
对于 40%的评测用例，|s|≤300；
对于 70%的评测用例，|s|≤5000；
对于所有评测用例，1≤|s|≤10^6，字符串中仅包含小写字母。

输入样例：

azaazaz

输出样例：

78

思路：很经典的dp问题 ，如下图，分析清楚状态集合

• f(i,0)表示不选择第i个字符的最大价值
• f(i,1)表示选择第i个字符的最大价值

最终的价值就是f(i,0)和f(i,1)中较大的一个

最后确定状态转移方程：

dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
dp[i][1]=dp[i-1][0]+str[i]-'a'+1;

 

完整代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1000010;
char str[N];
int dp[N][2];
 
int main(){
    cin>>str+1;
    int n=strlen(str+1);
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-1][0]+str[i]-'a'+1;
    }
    int res= max(dp[n][0],dp[n][1]);
    cout<<res<<endl;
}