松散子序列（寒假每日一题+DP)_松散子序列题目是什么意思

题目

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

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

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

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

输入格式

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

输出格式

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

数据范围

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

输入样例

azaazaz

输出样例

78

题目思路

其中题目中的“

假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 p(i) 个字符。

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

”这句话表示我们在选择字符时不能选择相邻的字符

        方法一：状态机DP

        方法二：一维DP

源代码

        方法一（状态机DP）

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 1e6+10;
 
char str[N];
int f[N][2];
 
int main()
{
    scanf("%s",str+1);
    
    int n=strlen(str+1);
    
    for(int i=1;i<=n;i++)
    {
        f[i][0]=max(f[i-1][0],f[i-1][1]);
        f[i][1]=f[i-1][0]+str[i]-'a'+1;
    }
    
    printf("%d",max(f[n][0],f[n][1]));
    return 0;
}

        方法二（其中用到了滚动数组，当然也可以不使用）

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 1e6+10;
 
char str[N];
int f[3];//滚动数组
 
int main()
{
    scanf("%s",str+1);
    
    int n=strlen(str+1);
    
    for(int i=1;i<=n;i++)
    {
        f[i%3]=max(f[(i-2)%3]+str[i]-'a'+1,f[(i-1)%3]);
    }
    
    printf("%d",f[n%3]);
    return 0;
}