AcWing 5406. 松散子序列
原题链接
中等
作者:
m_math
,
2024-04-11 16:03:15
,
所有人可见
,
阅读 4
跟大盗阿福很像,用状态机DP或者线性DP,此处用状态机
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1000010;
string s;
int f[N][2];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> s;
int n = (int)s.size();
s = " " + s;
f[1][0] = 0,f[1][1] = s[1] - 'a' + 1;
for(int i = 2;i <= n;i++)
{
f[i][0] = max(f[i - 1][1],f[i - 1][0]);
f[i][1] = f[i - 1][0] + s[i] - 'a' + 1;
}
cout << max(f[n][0],f[n][1]) << endl;
return 0;
}