第十四届蓝桥杯省赛PythonB组

思路:

// f[i] 定义为从前 i 个中选的最大价值
// 如果不选，那么从前 i - 1 转移而来 f[i] = f[i - 1];
// 如果选，那么 i - 1不能选，从前 i - 2 转移而来 ，所以 f[i - 2] + str[i] - 'a' + 1
// 至于为什么不是从前 i - 2 , i - 3 ... 0中的某个转移而
// 本来是需要 for(int i = 0 ; i <= i - 2 ; i ++) 循环一边的
// 因为我们在枚举到 i 时，i - 2 其实已经得到最小值了，若是从 i - 2 转移，一定要比从 i - 3转移更优
// 因为 如果从i - 3 转移更优的话，f[i - 2] 一定是等于 f[i - 3] 的，因为每次都得判断 i?
// 如果 i - 3 不是最优的，也就是需要 i - 2，那么从f[i - 2]转移更优一点
// 故综上所述，i - 2 一定更优，所以直接从 i - 2 转移即可

?

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

char str[N];
int f[N];

int main()
{
    cin >> str + 1;
    int n = strlen(str + 1);
    
    memset(f , -0x3f , sizeof f);
    f[0] = 0;
    int res = -1;
    for(int i = 1 ;i <= n ; i ++)
    {
        f[i] = max(f[i - 1] , f[i - 2] + str[i] - 'a' + 1);
        res = max(res , f[i]);
    }
    cout << res << endl;
    
    return 0;
}