AcWing 5406. 松散子序列 状态机模型
原题链接
中等
作者:
Snrise
,
2024-04-05 10:05:08
,
所有人可见
,
阅读 1
#pragma GCC optimize(3)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1000010;
char s[N];
int w[N];
int f[N][2];
// f[i][0]表示不以s[i]结尾的松散子序列的最大价值;
// f[i][1]表示以s[i]结尾的松散子序列的最大价值;
int n, ans;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> (s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; i++)
{
w[i] = s[i] - 'a' + 1;
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];
}
cout << max(f[n][0], f[n][1]) << endl;
return 0;
}