← 返回题目列表

AtCoder · tessoku_book_dk

B38. 草高地

中文机器翻译题面 查看原题

配点: 1000 点

問題文

N 草丛排成一排, 它们的编号最大为1 从 N 。 每株植物的高度为 由大于或等于 1 的整数值表示,以及有关它的以下信息: S_1,S_2,\cdots,S_{N-1} 是已知的。

  • S_i = 'A' :草 i 更多草 i + 1 确实更高
  • S_i = 'B' :草 i 更多草 i + 1 确实更低 打印

N 草的最小可能高度总和。 仅包含

制約

  • 1 \leq N \leq 3000
  • N 是一个整数
  • S 是 由于它被视为 'A' 和 即使增加或减少 'B' 仅由 N-1 字符串

入力

输入是按以下格式从标准输入给出的。

N
S

出力

请将您的答案输出为整数。


入力例 1

7
AABBBA

出力例 1

15

草的各个高度 1, 2, 4, 3, 2, 1, 2 是草的最小总高度的状态。