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

枫原万叶 · 2025-04-29 13:29:15 · 题解

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

分析

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

很明显是一道动态规划，我们考虑 dp_i 是长度为 i 的字符串的最大价值，那么对于当前状态，要么选当前这个位置的字母，反之则不选，如果选择了则需要考虑往前选 2 个还是 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;
}