AcWing:5406. 松散子序列

标签:DP

描述

给定一个仅含小写字母的字符串 s，假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi 个字符。

我们定义 s 的一个松散子序列为：对于 i>1 总是有 pi−pi−1 ≥ 2。

设一个子序列的价值为其包含的每个字符的价值之和（a∼z 分别为 1∼26）。

求 s 的松散子序列中的最大价值。

输入格式

输入一行包含一个字符串 s。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 20% 的评测用例，|s|≤10；
对于 40% 的评测用例，|s|≤300；
对于 70%的评测用例，|s|≤5000；
对于所有评测用例，1≤|s|≤10^6，字符串中仅包含小写字母。

输入样例：

azaazaz

输出样例：

78

 讲讲思路

   因为是要至少隔一个才可以取,不能连续取,那么只要是当前取,就拿上次不取的值加上这次的值即可,最后要记得比较,因为要看最后取或不取的max.

以下是AC代码:

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

using namespace std;
/* 定义 */
const int N = 1e6 + 10;
/* dp数组 */
int f[N][2];

int main()
{
    /* 读取 */
    string s;
    cin >> s;
    
    /* 初始化dp数组 */
    /* 0是不取,1是取 */
    f[0][0] = 0;
    f[0][1] = int(s[0] - 'a' + 1);
     
    /* 核心 */
    /* 由于不能取连续的,所以取只能拿上次没取的 */
    for (int i = 1; i < s.size(); i ++ )
    {
            f[i][0] = max(f[i - 1][0] , f[i - 1][1]);
            f[i][1] = f[i - 1][0] + int(s[i] - 'a' + 1);
    }
    
    /* 输出比较 */ 
    cout << max(f[s.size() - 1][0] , f[s.size() - 1][1]);
    return 0; //好习惯捏
}