실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 1024 MB |
"Pareidolia"란 실제로 존재하지 않는 이미지에서 익숙한 패턴이 보이는 현상입니다.
예를 들어, 구름에서 동물,얼굴 혹은 다른 물체의 형태를 보는 것과 같은 현상입니다.
bessie라는 애완견을 키우는 다현은, 영어 단어를 볼때 자신의 애완견의 이름과 관련된 패턴을 종종 발견하게 됩니다.
예를 들어, 그녀가 문자열 'bqessiyexbesszieb'를 보면, 다현의 눈에는 이룹 문자가 무시되고 그녀의 눈에는 'bessiexbessieb'만 보입니다.
즉, 'bessie'라는 연속된 부분의 문자열 두 개를 포함하는 문자열이 보입니다.
길이가 최대 인 a-z 문자로 이루어진 문자열이 주어졌을 때, 각 문자마다 삭제 비용이 존재합니다.
주어진 문자열에서 문자를 삭제하여 "bessie"라는 연속된 부분 문자열을 최대한 많이 만들어야합니다. "bessie"와 같은 부분 문자열의 최대 개수와, 이를 형성하기 위해 삭제해야하는 문자의 최소 총 비용을 계산하세요.
첫 번째 줄에는 문자열이 주어집니다. 두 번째 줄에는 각 문자와 연관된 삭제 비용(범위 의 정수)이 주어집니다.
연속된 부분 문자열의 최대 발생 횟수와 이 횟수를 생성하기 위한 최소 비용입니다.
besssie 1 1 5 4 6 1 1
1 4
bebesconsiete 6 5 2 3 6 5 7 9 8 1 4 5 1
1 21
besgiraffesiebessibessie 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 7
's'를 4번 위치에서 삭제하여 전체 문자열을 'bessie'로 만들 수 있습니다. 4번 위치에서 문자는 의 비용을 가지므로, 정답은 'bessie'의 인스턴스에 대한 의 비용이며, 이것이 할 수 있는 최선입니다.
입력 예시:
bebesconsiete
6 5 2 3 6 5 7 9 8 1 4 5 1
출력 예시:
1
21
'con'을 5-7번 위치에서 삭제하면 보이는 문자열은 'bebessiete'가 됩니다. 이제 이 문자열은 'bessie'를 가지게 됩니다. 문자 5-7은 비용이 이므로, 우리의 답은 비용 에 대한 'bessie'의 인스턴스가 되며, 이것이 우리가 할 수 있는 최선입니다.
입력 예시:
besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
출력 예시:
2
7
이 샘플은 두 번째 서브 과제의 제약 조건을 만족합니다.
4-10 위치에 있는 'giraffe'를 삭제하여 문자열을 'bessiebessibessie'로 만들 수 있습니다. 즉, 'bessie'가 시작과 끝에 있게 됩니다. 'giraffe'는 7개의 문자를 가지고 모든 문자가 비용이 이므로, 우리의 답은 'bessie'의 인스턴스에 대한 비용 이며, 이것이 우리가 할 수 있는 최선입니다.
점수: