cinador   2년 전

(문제를 보다 명확하게 하기 위해 본래 문제의 설정은 대부분 생략했습니다.) 

ㅤ

문제

문자열 'RGB' 를 0개 이상 이어붙여 만든 문자열을 'RGB 문자열' 이라고 하자. 예를 들어, 빈 문자열, 'RGB', 'RGBRGBRGB' 는 RGB 문자열이고, 'R', 'RGBRG', 'GBRGBR' 은 RGB 문자열이 아니다.

길이가 1 이상인 임의의 문자열에 대해, 아래 3개의 작업 중 하나를 선택해 문자열에 적용시킬 수 있다고 하자.

  • 비용을 A만큼 들여, 문자열의 가장 앞에 있는 문자 하나를 제거한다.
  • 비용을 B만큼 들여, 문자열의 가장 뒤에 있는 문자 하나를 제거한다.
  • 비용을 C만큼 들여, 문자열의 임의의 위치에 있는 문자 하나를 원하는 문자로 바꾼다.

선택한 작업의 결과로 얻은 문자열의 길이가 1 이상이라면, 위 과정을 다시 반복할 수 있다.

길이가 N이고 'R', 'G', 'B' 로만 이루어진 문자열 S와 각 작업에 필요한 비용이 주어질 때, 위 과정을 원하는 만큼 반복하여, 주어진 문자열을 RGB 문자열로 바꾸는 데에 필요한 최소 비용을 구하여라.

ㅤ

입력

입력은 다음과 같은 형식을 갖는다.

N
S
A   B   C

ㅤ

출력

주어진 문자열을 RGB 문자열로 바꾸는 데에 필요한 최소 비용을 출력한다.

ㅤ

제한

  • 1 ≤ N ≤ 200,000.
  • S는 길이가 N인 문자열이며, S의 각 문자는 'R', 'G', 'B' 중 하나이다.
  • 1 ≤ A, B, C ≤ 109.
  • N, A, B, C는 모두 정수이다.

ㅤ

서브태스크

  1. (4점)   N ≤ 3.
  2. (22점) N ≤ 300.
  3. (19점) N ≤ 10,000.
  4. (9점)   N은 3의 배수, A = 109, B = 109, C = 1.
  5. (10점) A = 109, B = 109, C = 1.
  6. (36점) 추가적인 제약이 없다.

ㅤ

ㅤ

ㅤ

예제 1 설명

preview

ㅤ

예를 들어, 다음과 같은 4번의 작업으로 주어진 문자열을 RGB 문자열로 바꿀 수 있다.

  1. 비용을 3만큼 들여, 문자열의 가장 앞에 있는 문자 하나를 제거한다. 이 작업 이후 문자열은 'RBBRG' 가 된다.
  2. 비용을 4만큼 들여, 문자열의 가장 뒤에 있는 문자 하나를 제거한다. 이 작업 이후 문자열은 'RBBR' 이 된다.
  3. 비용을 4만큼 들여, 문자열의 가장 뒤에 있는 문자 하나를 제거한다. 이 작업 이후 문자열은 'RBB' 가 된다.
  4. 비용을 5만큼 들여, 문자열의 두 번째 문자를 'G' 로 바꾼다. 이 작업 이후 문자열은 "RGB' 가 된다.

16 미만의 비용으로 주어진 문자열을 RGB 문자열로 바꿀 수 없으므로, 16을 출력한다.

ㅤ

예제 2 설명

preview

ㅤ

예를 들어, 다음과 같은 3번의 작업으로 주어진 문자열을 RGB 문자열로 바꿀 수 있다.

  1. 비용을 1만큼 들여, 문자열의 두 번째 문자를 'G' 로 바꾼다. 이 작업 이후 문자열은 'BGG' 가 된다.
  2. 비용을 1만큼 들여, 문자열의 세 번째 문자를 'B' 로 바꾼다. 이 작업 이후 문자열은 'BGB' 가 된다.
  3. 비용을 1만큼 들여, 문자열의 첫 번째 문자를 'R' 로 바꾼다. 이 작업 이후 문자열은 'RGB' 가 된다.

 3 미만의 비용으로 주어진 문자열을 RGB 문자열로 바꿀 수 없으므로, 3을 출력한다.

ㅤ

예제 3 설명

preview

ㅤ

예를 들어, 다음과 같은 3번의 작업으로 주어진 문자열을 RGB 문자열로 바꿀 수 있다.

  1. 비용을 9만큼 들여, 문자열의 가장 앞에 있는 문자 하나를 제거한다. 이 작업 이후 문자열은 'RB' 가 된다.
  2. 비용을 9만큼 들여, 문자열의 가장 앞에 있는 문자 하나를 제거한다. 이 작업 이후 문자열은 'B' 가 된다.
  3. 비용을 9만큼 들여, 문자열의 가장 앞에 있는 문자 하나를 제거한다. 이 작업 이후 문자열은 빈 문자열이 된다.

27 미만의 비용으로 주어진 문자열을 RGB 문자열로 바꿀 수 없으므로, 27을 출력한다. 빈 문자열도 RGB 문자열에 포함된다는 것에 주의한다.

ㅤ

예제 4 설명

preview

ㅤ

주어진 문자열이 이미 RGB 문자열이므로, 0을 출력한다.

댓글을 작성하려면 로그인해야 합니다.