''' 参考了这位大佬的思路:https://blog.csdn.net/qq_22522375/article/details/107771758 如果有发现代码思路有问题,欢迎指教。 给定一个a-f组成的字符串,对其进行删除,要求所有的a在c和e之前且所有的c在e之前, 所有的b在d和f之前且所有的d在f之前,求删除后满足串的最大长度''' strs = input() l1,l2 = [],[] dict = {'b':'a','d':'c','f':'e'} for item in strs: if item in {'a','c','e'}: l1.append(item) else: l2.append(dict[item]) def helper(lists): length = len(lists) dp = [[0,0,0]for i in range(length)]#表示到当前点,以a/c/e结尾的最长子串 if lists[0]=='a': dp[0][0] = 1 elif lists[0]=='c': dp[0][1] = 1 else: dp[0][2] = 1 index = 1 for item in lists[1:]: if item == 'a': dp[index][0] = dp[index-1][0]+1#加一 dp[index][1] = dp[index - 1][1]#不变 dp[index][2] = dp[index - 1][2]#不变 elif item == 'c': dp[index][0] = dp[index - 1][0] #表示不考虑该点 dp[index][1] = max(dp[index-1][0],dp[index-1][1])+1 dp[index][2] = dp[index - 1][2] #表示删除该点 else: dp[index][0] = dp[index - 1][0] # 表示删除该点 dp[index][1] = dp[index - 1][1]# 表示删除该点 dp[index][2] =max(dp[index-1])+1#不删除 index+=1 return max(dp[length-1]) print(helper(l1)+helper(l2))
全部评论
(1) 回帖