分数: 400 点
问题陈述
给你一个字符串 S 长度 N 组成 0 和 1.
一个字符串 T 长度 N 组成 0 和 1 是 好字符串 当且仅当满足以下条件:
- 正好有一个整数 i 这样 1 \leq i \leq N - 1 和 i-th 和 自记录开始以来,第 (i + 1)第一个字符 T 是相同的。
对于每个 i = 1,2,\ldots, N,您可以选择是否执行一次以下操作:
- 如果 i- 第一个字符 S is
0,替换为1,反之亦然。如果执行该操作,其成本为 C_i.
找出制造所需的最低总成本 S 一个好字符串。
约束
- 2 \leq N \leq 2 \times 10^5
- S 是一个长度为 N 组成
0和1. - 1 \leq C_i \leq 10^9
- N 和 C_i 是整数。
输入
输入由标准输入按以下格式给出:
N S C_1 C_2 \ldots C_N
输出
打印答案。
示例输入 1
5 00011 3 9 2 6 4
示例输出 1
7
执行以下操作 i = 1, 5 并且不执行它 i = 2, 3, 4 使 S = 10010,这是一个很好的字符串。本例中产生的费用为 7,并且不可能使 S 一个好的字符串小于 7,所以打印 7.
示例输入 2
4 1001 1 2 3 4
示例输出 2
0
示例输入 3
11 11111100111 512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427
示例输出 3
2286846953