AcWing 5406. 松散子序列
原题链接
中等
作者:
陈驰水
,
2024-04-09 19:37:37
,
所有人可见
,
阅读 2
蓝桥杯 DP状态机板子
// 经典状态机 唯一要注意的是 dp[n - 1][1] 不一定最大 也可能是 dp[n - 2][1]
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int getVal(char c) {
return c - 'a' + 1;
}
int main() {
string input;
cin >> input;
int n = input.size();
// 注意特判下单元素 考试要想到
// 云课上有一个样例
if (n == 1) {
cout << getVal(input[0]) << endl;
return 0;
}
vector<vector<int>>dp(n, vector<int>(2, 0));
dp[0][1] = getVal(input[0]);
dp[1][1] = max(dp[0][1], getVal(input[1]));
for (int i = 2; i < n; i++) {
dp[i][0] = max({ dp[i][0], dp[i - 2][1] , dp[i - 1][0]});
dp[i][1] = max({ dp[i][1], dp[i][0] + getVal(input[i])});
}
cout << max(dp[n - 1][1], dp[n - 2][1]) << endl;
return 0;
}