给定一个仅含小写字母的字符串 $ s $,假设 $ s $ 的一个子序列 $ t $ 的第 $ i $ 个字符对应了原字符串中的第 $ p_i $ 个字符。
我们定义 $ s $ 的一个松散子序列为:对于 $ i > 1 $ 总是有 $ p_i-p_{i-1} \ge 2 $。
设一个子序列的价值为其包含的每个字符的价值之和($ a \sim z $ 分别为 $ 1 \sim 26 $)。
求 $ s $ 的松散子序列中的最大价值。
输入格式
输入一行包含一个字符串 $ s $。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 $ 20\% $ 的评测用例,$ |s| \le 10 $;
对于 $ 40\% $ 的评测用例,$ |s| \le 300 $;
对于 $ 70\% $ 的评测用例,$ |s| \le 5000 $;
对于所有评测用例,$ 1 \le |s| \le 10^6 $,字符串中仅包含小写字母。
输入样例:
azaazaz
输出样例:
78
状态DP方法
在这个问题中,我们使用状态DP来寻找一个字符串的松散子序列,以使得子序列的字符价值之和最大化。状态DP的关键在于如何定义状态和状态之间的转移关系。
状态定义
我们定义了两个状态数组 dp[i][0]
和 dp[i][1]
:
dp[i][0]
表示以第 ( i ) 个字符结尾的松散子序列的最大价值,且第 ( i ) 个字符未被选中。dp[i][1]
表示以第 ( i ) 个字符结尾的松散子序列的最大价值,且第 ( i ) 个字符被选中。
状态转移
状态转移考虑了如何从先前的状态推导出当前状态的最大价值。状态转移方程如下:
dp[i + 1][0] = max(dp[i][0], dp[i][1])
:这表示如果第 ( i + 1 ) 个字符未被选中,那么以它结尾的松散子序列的最大价值等于前一个字符被选中和未被选中情况下的最大值。dp[i + 1][1] = dp[i][0] + s[i] - 'a' + 1
:这表示如果第 ( i + 1 ) 个字符被选中,那么以它结尾的松散子序列的最大价值等于前一个字符未被选中的最大价值加上当前字符的价值。
初始化
dp[0][1]
初始化为字符串第一个字符的价值。dp[0][0]
为0,因为如果第一个字符未被选中,子序列的价值为0。
解决问题
遍历整个字符串,根据状态转移方程更新 dp[i][0]
和 dp[i][1]
。最后,结果是 max(dp[s.size() - 1][0], dp[s.size() - 1][1])
,即最后一个字符作为结尾时,被选中和未被选中情况下的最大价值。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
// dp[i][0] 表示以i为结尾的松散子序列的最大价值,且i未被选中
// dp[i][1] 表示以i为结尾的松散子序列的最大价值,且i被选中
// 则dp[i + 1][0] = max(dp[i][0], dp[i][1])
// dp[i + 1][1] = dp[i][0] + s[i] - 'a' + 1
const int N = 1e6 + 10;
int dp[N][2];
int main() {
string s;
cin >> s;
dp[0][1] = s[0] - 'a' + 1;
for (int i = 1; i < s.size(); i ++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + s[i] - 'a' + 1;
}
cout << max(dp[s.size() - 1][0], dp[s.size() - 1][1]) << endl;
}
线性DP
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
// dp[i] 表示以i为结尾的松散子序列的最大价值
// 不选第i个字母 dp[i] = dp[i - 1]
// 选第i个字母, dp[i] = dp[i - 2] + s[i] - 'a' + 1
const int N = 1e6 + 10;
int dp[N];
int main() {
string s;
cin >> s;
dp[0] = s[0] - 'a' + 1;
if (s.length() < 2) {
cout << dp[0] << endl;
return 0;
}
else {
dp[1] = max(dp[0], s[1] - 'a' + 1);
for (int i = 2; i < s.size(); i ++) {
dp[i] = max(dp[i - 1], dp[i - 2] + s[i] - 'a' + 1);
}
cout << max(dp[s.size() - 2], dp[s.size() - 1]) << endl;
}
}