自动搬运

查看原文

来自洛谷，原作者为

	枫原万叶 我无法追寻每一只知更鸟坠落的轨迹,我也不是经常会想起你

搬运于2025-08-24 23:15:05，当前版本为作者最后更新于2025-04-29 13:29:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P12379 [蓝桥杯 2023 省 Python B] 松散子序列 题解

分析

题目大意就是说选择几个字母（两两字母不应相邻，至少空一个字母），然后把选择的字母的价值相加（字母的价值就是字母在字母表的位置）。

很明显是一道动态规划，我们考虑 $dp_i$ 是长度为 $i$ 的字符串的最大价值，那么对于当前状态，要么选当前这个位置的字母，反之则不选，如果选择了则需要考虑往前选 $2$ 个还是 $3$ 个，因为再大就可以继续在中间选择了，然后还要加上当前位置的价值。

综上所述，我们就可以得到状态转移方程。

$$dp_i = \max (dp_{i-1},val_i+\max(dp_{i-2},dp_{i-3})) $$

代码

#include<bits/stdc++.h>
using namespace std;
int dp[1000010];

int val(char c){
    return int(c-'a'+1);
}

int main(){
    string s;
    cin>>s;
    int n = s.size();
    if(n == 0){
        cout << 0;
        return 0;
    }
    
    dp[0] = 0;
    dp[1] = val(s[0]);
    if(n >= 2){
        dp[2] = max(val(s[1]), dp[1]);
    }
    
    for(int i = 3; i <= n; i++){
        dp[i] = max(dp[i-1], val(s[i-1]) + max(dp[i-2], dp[i-3]));
    }
    
    cout << dp[n];
    return 0;
}