分数: 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