Задача #2025
Работа со строками
(П. Говоров) В файле содержится строка длиной не более 106 из букв A,B,C.
Определите в прилагаемом файле максимальную длину подпоследовательности, составленную конкатенацией из следующих подстрок (могут использоваться любое количество раз): ABA, CB, AC, BB, ABC, BCB, BA, AB.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
71
f = open('24-14100.txt')
s = f.readline()
dp = [0] * len(s)
prim = ['ABA', 'CB', 'AC' , 'BB', 'ABC', 'BCB', 'BA', 'AB']
for i in range(1, len(s)):
for j in prim:
if i >= len(j) - 1:
if s[i-len(j)+1:i+1]==j:
dp[i] = max(dp[i], dp[i-len(j)] + len(j))
print(max(dp))