문제
우리는 메모장에 길이 N의 문자열 S를 적고 싶다.
단순히 N개의 타이핑을 통해 문자열을 적을 수도 있지만, 이는 너무 비효율적이다.
우리는 다음의 3가지 방법으로 문자열을 조작할 수 있다.
현재 화면에 보이는 문자열이 X이고, 클립보드에 저장된 문자열이 Y라고 하자.
1) 문자열의 끝에 문자 하나를 추가한다(X=X+c). 이 연산은 A의 추가적인 피로도가 든다.
2) 현재 문자열을 클립보드로 자른다(Y=X, X=""). 이 연산은 B의 추가적인 피로도가 든다.
3) 현재 문자열에 클립보드에 저장되어 있는 문자열을 붙인다(X=X+Y). 이 연산은 C의 추가적인 피로도가 든다.
A, B, C의 값이 주어질 때, S를 만들 수 있는 최소의 피로도를 구하시오.
입력
첫 줄에 N이 주어진다. (1<=N<=2500)
그 다음 줄에 만들고 싶은 길이 N의 문자열 S가 주어진다. (각 문자는 모두 영어 소문자이다.)
그 다음 줄에 A가 주어진다. (1<=A<=10^9)
그 다음 줄에 B가 주어진다. (1<=B<=10^9)
그 다음 줄에 C가 주어진다. (1<=C<=10^9)
출력
S를 만들 수 있는 최소의 피로도를 구하시오.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 2점 | N=3 |
| #2 | 5점 | S는 'a'로만 이루어져있다. |
| #3 | 13점 | N<=30 |
| #4 | 10점 | N<=200 |
| #5 | 32점 | N<=1000 |
| #6 | 38점 | 제한 없음 |
예제1
입력
11
mississippi
10
5
2
출력
88
예제2
입력
16
aaaaaaaaaaaaaaaa
1
1
1
출력
9
출처
JOI Spring Camp 2022 Day 2