蓝桥杯2023年-松散子序列（dp）
题目描述
给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符 对应了原字符串中的第 pi 个字符。我们定义 s 的一个松散子序列为：对于 i > 1 总是有 pi − pi−1 ≥ 2 。设一个子序列的价值为其包含的每个字符的价值之和 ( a ∼ z 分别为 1 ∼ 26 ) 。
求 s 的松散子序列中的最大价值。
思路
只要想到要用dp代码就不难写了（当然还需要先读懂题）。
dp[i]表示前i个字母可以取到的最大价值。
则分成两种情况：
1、取第i个字母：则最大值为dp[i-2]+s[i]-'a'+1;
2、不取第i个字母：则最大值为dp[i-1]
两种情况取最大值即可。
代码
#include<bits/stdc++.h>
using namespace std;
// #define int long long
// #define pii pair<long long,long long>
int dp[1000006];
signed main(){
string s;cin>>s;
int n=s.size();
dp[0]=s[0]-'a'+1;
dp[1]=max(dp[0],s[1]-'a'+1);
for(int i=2;i<n;i++){
dp[i]=max(dp[i-1],dp[i-2]+s[i]-'a'+1);
}
cout<<dp[n-1];
}