← 返回题目列表

AtCoder · arc211_c

C. 森林

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

分数: 600 点

问题陈述

给你一个正整数 N,一个字符串 S 长度 N 组成 # 和 .,以及长度-N 正整数序列 R=(R_1,R_2,\dots,R_N).

有一片森林, N 部分排列在一条水平线上。这些部分已编号 1,2,\dots,N 从左到右。

有些路段有树木。具体来说,部分 i 有一棵树当且仅当 i- 第一个字符 S is #。保证以下操作至少可以执行一次。

您可以根据需要多次重复以下操作:

  • 选择两个没有树的部分。让部分 i 和 j (其中 i < j) 是从左到右选择的部分。然后,部分之间的所有树 i 和 j 被移除,您将获得奖励 R_i+R_j.

此处,您无法执行不删除任何树的操作。

查找执行该操作的方法数量 第一 操作以实现最大可能的总奖励。当且仅当存在以一种方式选择但不以另一种方式选择的部分时,两种方式才被认为是不同的。

约束

  • 3\leq N\leq 2\times 10^5
  • 的长度 S is N,每个字符是 # or ..
  • 1\leq R_i\leq 10^9 (1\leq i\leq N)
  • 该操作至少可以执行一次。
  • N 和 R_i 是整数。

输入

输入由标准输入按以下格式给出:

N
S
R_1 R_2 \dots R_N

输出

输出答案。


示例输入 1

8
...###..
20 25 1 1 30 2 1 1

示例输出 1

2

执行第一个操作有六种方式,如下:

  • 选择部分 1 和 7。各路段的树木 4,5,6 被移除,您将获得奖励 21.
  • 选择部分 1 和 8。各路段的树木 4,5,6 被移除,您将获得奖励 21.
  • 选择部分 2 和 7。各路段的树木 4,5,6 被移除,您将获得奖励 26.
  • 选择部分 2 和 8。各路段的树木 4,5,6 被移除,您将获得奖励 26.
  • 选择部分 3 和 7。各路段的树木 4,5,6 被移除,您将获得奖励 2.
  • 选择部分 3 和 8。各路段的树木 4,5,6 被移除,您将获得奖励 2.

无论执行哪一个操作,所有树都会被删除,因此无法执行第二次操作。最大可能的总奖励是 26.


示例输入 2

5
.#.#.
211 182 192 182 211

示例输出 2

2

最大可能的总奖励是 825.

请注意,目标不是最大化第一次操作中获得的奖励。如果您选择部分 1 和 5 首先,你可以获得奖励 422,但之后无法进行任何操作,总奖励达不到 825.


示例输入 3

11
#..#.##.#..
192 192 192 211 182 192 182 192 182 211 182

示例输出 3

3