题目详情题解（0）讨论（0）提交记录（0）

AT_abc346_d.[ABC346D] Gomamayo Sequence

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由 0 和 1 组成、长度为 NN 的字符串 SS。

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

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

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

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

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

输入格式

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

NN
SS
C1 C2 … CNC_1\ C_2\ \ldots\ C_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    5
00011
3 9 2 6 4

    输出#1

    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

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • SS 是长度为 NN 的、仅包含 0 和 1 的字符串
  • 1≤Ci≤1091 \leq C_i \leq 10^9
  • NN、CiC_i 均为整数

样例解释 1

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

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页