5337 : B38 - 풀의 높이
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$ N $ 개의 풀이 일렬로 나열되어 있으며, $ 1 $ 부터 $ N $ 까지 번호가 매겨져 있습니다.
각 풀의 높이는 $ 1 $ 이상의 정수이며, 다음 정보 $ S_1, S_2, \dots, S_{N-1}$ 이 주어집니다.
$ S_i = 'A'$ 일 때: 풀 $ i $ 보다 풀 $ i+1 $ 이 엄격히 높음
$ S_i = 'B'$ 일 때: 풀 $ i $ 보다 풀 $ i+1 $ 이 엄격히 낮음
$ N $ 개의 풀 높이의 합으로 가능한 최솟값을 출력하십시오.
[제약 조건]
• $1 \le N \le 3000$
• $N$ 는 정수
• $S$ 는 'A' 및 'B' 만으로 이루어집니다. $N-1$ 자의 문자열
각 풀의 높이는 $ 1 $ 이상의 정수이며, 다음 정보 $ S_1, S_2, \dots, S_{N-1}$ 이 주어집니다.
$ S_i = 'A'$ 일 때: 풀 $ i $ 보다 풀 $ i+1 $ 이 엄격히 높음
$ S_i = 'B'$ 일 때: 풀 $ i $ 보다 풀 $ i+1 $ 이 엄격히 낮음
$ N $ 개의 풀 높이의 합으로 가능한 최솟값을 출력하십시오.
[제약 조건]
• $1 \le N \le 3000$
• $N$ 는 정수
• $S$ 는 'A' 및 'B' 만으로 이루어집니다. $N-1$ 자의 문자열
입력 설명
첫째 줄에 $ N $ 이 주어집니다.
둘째 줄에 문자열 $ S $ 가 주어집니다.
둘째 줄에 문자열 $ S $ 가 주어집니다.
출력 설명
풀 높이 합의 최솟값을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7
AABBBA
출력 예시
COPY
복사되었습니다!
복사되었습니다!
15도움
풀의 높이가 각각 $ 1, 2, 4, 3, 2, 1, 2 $ 인 상태가 풀 높이의 합이 최소가 됩니다.