【Coding】寒假每日一题Day.6. 松散子序列

题目来源

题目来自于AcWing平台：https://www.acwing.com/problem/content/5409/。
以blog的形式记录程序设计算法学习的过程，仅做学习记录之用。

题目描述

输入输出格式与数据范围+样例

思路

经过快一周的算法复习，这道题已经基本能独立思考出来了。显然这是一个需要使用DP求解的问题，在最后求状态转移方程的时候，对于“不选当前字符”的状态有些不确定，遂参考了题解：https://www.acwing.com/solution/content/221129/。

为什么说这是一个DP的问题，因为它需要使用DP的提示非常明显。要求的是子串最大的价值，而子串当中的字母来源于原串，原串中的字母不能连续取（至少间隔一个字母），因此将前缀的最大价值看作是状态，最优解一定同时出现在两个集合中，即——选取当前字符/不选当前字符。

那么问题就迎刃而解了，维护好状态转移数组即可。如果不选当前字符，那么当前前缀的最大价值一定就是上一个字符对应的前缀的最大价值。

Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

typedef string str;

const int maxn = 1e6 + 5;
int f[maxn] = {0};
int s[maxn] = {0};

str st;

int main()
{
    cin >> st;
    
    int n = st.length();
    for(int i=0;i<=n;i++){
        s[i+1] = (int)(st[i] - 'a') + 1;
    }
    
    f[1] = s[1];
    
    for(int i=2;i<=n;i++){
        f[i] = max(f[i-1], f[i-2] + s[i]);
    }
    cout << f[n];
    return 0;
}