[R61D]01串分割 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的 $01$ 字符串 $s$。

我们定义一个字符串是合法的，当且仅当它可以被分割为若干个互不重叠的连续子串，且每个子串均为 1、01 或 001 中的一种。

现在你需要通过修改原字符串 $s$，使其变为一个合法字符串。在每次修改中，你可以选择翻转字符串中某一位的字符（即 $0$ 变为 $1$，或 $1$ 变为 $0$）。已知翻转第 $i$ 个字符所需的代价为 $a_i$。

请计算将整个字符串 $s$ 修改为合法字符串所需的最小总代价。

格式

输入格式

第一行包含一个正整数 $n$，表示字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的 $01$ 字符串 $s$。

第三行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，相邻两个数之间用空格隔开，表示翻转第 $i$ 个位置字符的代价。

输出格式

输出一行一个整数，表示将字符串修改为合法字符串的最小总代价。

样例

样例输入 #1

4
0000
1 2 3 4

样例输出 #1

5

样例解释 #1

最优方案是将原字符串修改为 1001，该串可以成功分割为 1 和 001 两个合法的子串。 在这个过程中，我们需要翻转第 $1$ 个和第 $4$ 个字符，花费的代价之和为 $a_1 + a_4 = 1 + 4 = 5$。可以证明不存在代价更小的合法修改方案。

样例输入 #2

5
10100
10 20 30 40 50

样例输出 #2

50

样例解释 #2

观察发现，所有合法的编码块都以 1 结尾，因此合法字符串的末尾必定是 1。 为了得到最小代价，我们仅将末尾的 0 修改为 1，字符串变为 10101，该串可以分割为 1、01 和 01 三个合法子串。 花费的代价为 $a_5 = 50$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$	特殊性质
$1$	$20$	$15$	无
$2$	$20$	$10^6$	对于所有的 $1 \le i \le n$，都有 $s_i = \text{0}$ 且 $a_i = 1$
$3$	$60$		无

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$s$ 仅由字符 0 和 1 组成，$1 \le a_i \le 10^9$。