AT_abc346_d [ABC346D] Gomamayo Sequence

题目描述

给定一个由 0 和 1 组成、长度为 $N$ 的字符串 $S$。

定义一个由 0 和 1 组成、长度为 $N$ 的字符串 $T$，当且仅当满足以下条件时，$T$ 被称为好字符串：

• 存在且仅存在一个整数 $i$，满足 $1 \leq i \leq N-1$，使得 $T$ 的第 $i$ 个字符与第 $i+1$ 个字符相同。

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

• 如果 $S$ 的第 $i$ 个字符为 0，则可以将其变为 1；否则，将其变为 0。每进行一次操作，需要花费 $C_i$ 的代价。

请你求出将 $S$ 变为好字符串所需的最小总代价。

输入格式

输入通过标准输入给出，格式如下：

$N$
$S$
$C_1\ C_2\ \ldots\ C_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5
00011
3 9 2 6 4

输出 #1

7

输入输出样例 #2

输入 #2

4
1001
1 2 3 4

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

2286846953

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $S$ 是长度为 $N$ 的、仅包含 0 和 1 的字符串
• $1 \leq C_i \leq 10^9$
• $N$、$C_i$ 均为整数

样例解释 1

对 $i=1,5$ 进行操作，对 $i=2,3,4$ 不进行操作，此时 $S=10010$，$S$ 是好字符串。此时总代价为 $7$，且无法以更小的代价将 $S$ 变为好字符串，因此输出 $7$。

由 ChatGPT 4.1 翻译