题目描述：
字符串T包含abcdef， T <
a只能在ce前面，c只能在e前面
b只能在df前面，d只能在f前面
问 最长子序列多长？
example：
afcaba = 4；
bbeeae = 5；
题解
分成两个字符串算总长，一个只包含ace，一个只包含bdf。以a结尾的只能从a转移过来，c可以从ac转移过来，e可以从ace转移过来。复杂度O(n)。
// // Created by ironzhou on 2020/8/3. // 字符串T包含abcdef， T < // a只能在ce前面，c只能在e前面 // b只能在df前面，d只能在f前面 // 问 最长子序列多长？ // example: afcaba = 4; bbeeae = 5 // #include <bits/stdc++.h> #define Size using namespace std; int main(){
string s; cin>>s; int dp1[Size][3],dp2[Size][3]; for(int i = 0 ; i < 3 ; i++) {
dp1[0][i] = 0; dp2[0][i] = 0; } int sum = 0; for(int i = 1 ; i <= s.size() ; i++) {
int k = i-1; for(int j = 0 ; j < 3; j++) {
dp1[i][j] = dp1[i-1][j]; dp2[i][j] = dp2[i-1][j]; } switch (s[k]) {
case 'a': dp1[i][0] = dp1[i-1][0] + 1; break; case 'b': dp2[i][0] = dp2[i-1][0] + 1; break; case 'c': dp1[i][1] = max(dp1[i-1][0]+1,dp1[i-1][1]+1); break; case 'd': dp2[i][1] = max(dp2[i-1][0]+1,dp2[i-1][1]+1); break; case 'e': dp1[i][2] = max(dp1[i-1][0]+1,dp1[i-1][1]+1); dp1[i][2] = max(dp1[i][2],dp1[i-1][2]+1); break; case 'f': dp2[i][2] = max(dp2[i-1][0]+1,dp2[i-1][1]+1); dp2[i][2] = max(dp2[i][2],dp2[i-1][2]+1); break; } for(int j = 0 ; j < 3; j++) {
for(int k = 0; k < 3 ; k++) {
sum = max(sum, dp1[i][j] + dp2[i][k]); } } } cout<<sum<<endl; return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/101676.html