레이팅 미적용파레이돌리아(Pareidolia)는 실제로는 존재하지 않는 익숙한 패턴을 이미지에서 보게 되는 현상이다. 예를 들어 구름에서 얼굴을 보는 것이다. 짐작할 수 있듯이, 농부 존은 항상 소들 곁에 있다 보니 일상 사물에서 소와 관련된 패턴을 자주 본다. 예를 들어 문자열 "bqessiyexbesszieb"를 보면, 농부 존의 눈은 일부 글자를 무시하고 "bessiexbessieb"만 보게 된다. 이 문자열은 "bessie"와 같은 연속 부분 문자열을 두 개 포함한다.
a-z 문자로만 이루어진 길이 \(2\cdot 10^5\) 이하의 문자열이 주어지고, 각 문자에는 삭제 비용이 있다. 이 문자열에서 0개 이상의 문자를 삭제하여 만들 수 있는 "bessie"와 같은 연속 부분 문자열의 최대 개수와, 이를 달성하기 위해 삭제해야 하는 문자들의 최소 총 비용을 계산하라.
출제자: Benjamin Qi
배점
- 입력 4-5: \(N\le 2000\)
- 입력 6-8: 모든 비용이 \(1\)이다.
- 입력 9-17: 추가 제약 조건이 없다.
출제자: Benjamin Qi
첫째 줄에 문자열이 주어진다. 둘째 줄에 각 문자에 대응하는 삭제 비용(범위 \([1,1000]\)의 정수)이 주어진다.
최대 등장 횟수와, 그 등장 횟수를 만들기 위한 최소 비용을 출력한다.
besssie
1 1 5 4 6 1 11
4By deleting the 's' at position 4 we can make the whole string "bessie". The
character at position 4 has a cost of \(4\), so our answer is cost \(4\) for \(1\)
instance of "bessie", which is the best we can do.
bebesconsiete
6 5 2 3 6 5 7 9 8 1 4 5 11
21By deleting the "con" at positions 5-7, we can make the string "bebessiete"
which has "bessie" in the middle. Characters 5-7 have costs \(5 + 7 + 9 = 21\), so
our answer is cost \(21\) for \(1\) instance of "bessie", which is the best we can
do.
besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12
7This sample satisfies the constraints for the second subtask.
By deleting the "giraffe" at positions 4-10, we can make the string
"bessiebessibessie", which has "bessie" at the beginning and the end. "giraffe"
has 7 characters and all characters have cost \(1\), so our answer is cost \(7\) for
\(2\) instances of "bessie", which is the best we can do.