Gomamayo Sequence

题目描述

你被给定一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串 $S$。 长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串 $T$ 当且仅当它满足以下条件时是一个好字符串：

存在且仅存在一个整数 $i$ 满足 $1 \leq i \leq N - 1$ 且 $T$ 的第 $i$ 个和第 $(i + 1)$ 个字符相同。

对于每个 $i = 1,2,\ldots, N$，你可以选择是否对以下操作执行一次：

如果 $S$ 的第 $i$ 个字符是 $0$，将其替换为 $1$，反之亦然。若执行该操作，其代价为 $C_i$。

求将 $S$ 变为一个好字符串所需的最小总代价。

输入格式

输入从标准输入按以下格式给出： $N$ $S$ $C_1$ $C_2$ $\ldots$ $C_N$

输出格式

输出答案。

5
00011
3 9 2 6 4

7

4
1001
1 2 3 4

0

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

2286846953

提示

$2 \leq N \leq 2 \times 10^5$ $S$ 是一个长度为 $N$ 的由 $0$ 和 $1$ 组成的字符串。 $1 \leq C_i \leq 10^9$ $N$ 和 $C_i$ 是整数。对 $i = 1, 5$ 执行操作而对 $i = 2, 3, 4$ 不执行操作会使 $S =$$10010$，这是一个好字符串。在这种情况下花费为 $7$，且不可能用小于 $7$ 的代价将 $S$ 变为好字符串，所以输出 $7$。

标签: AtCoder|abc346D

来源

AtCoder|abc346D