蓝桥杯2023年-松散子序列（dp）

本文主要是介绍蓝桥杯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];
}

这篇关于蓝桥杯2023年-松散子序列（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---