{"problem":{"name":"[省选联考 2022] 序列变换","description":{"content":"你手里有一个长度为 $2 n$ 的合法括号序列 $s$。$s$ 的每一个左括号有一个权值。 在你眼中，不同的括号序列带来的视觉美感不尽相同。因此，你对具有某一种结构的括号序列特别喜欢，而讨厌具有其他一些结构的括号序列。你希望对 $s$ 进行一些变换，以消除掉一些自己不喜欢的结构。 具体而言，形如 $\\texttt{(A()B)}$（其中 $\\texttt{A}$、$\\texttt{B}$ 均为","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8293"},"statements":[{"statement_type":"Markdown","content":"你手里有一个长度为 $2 n$ 的合法括号序列 $s$。$s$ 的每一个左括号有一个权值。\n\n在你眼中，不同的括号序列带来的视觉美感不尽相同。因此，你对具有某一种结构的括号序列特别喜欢，而讨厌具有其他一些结构的括号序列。你希望对 $s$ 进行一些变换，以消除掉一些自己不喜欢的结构。\n\n具体而言，形如 $\\texttt{(A()B)}$（其中 $\\texttt{A}$、$\\texttt{B}$ 均为合法括号序列，下同）的结构是你喜欢的，\n而形如 $\\texttt{(A)(B)}$ 的结构是你不喜欢的。你有两种操作来改变括号之间的位置。\n\n这两种操作如下：\n- 操作 1：交换形如 $\\texttt{p(A)(B)q}$ 的串中 $\\texttt{A}$ 和 $\\texttt{B}$ 之间的两个括号，变换为 $\\texttt{p(A()B)q}$（其中 $\\texttt{p}$、$\\texttt{q}$ 为任意串，可以为空，但不一定分别为合法括号序列，下同），它的代价为 $x$ 乘 $\\texttt{(A)}$ 中第一个左括号的权值加上 $y$ 乘 $\\texttt{(B)}$ 中第一个左括号的权值，其中 $x, y \\in \\{0, 1\\}$；\n- 操作 2：交换形如 $\\texttt{pABq}$ 的串中的 $\\texttt{A}$ 和 $\\texttt{B}$，变换为 $\\texttt{pBAq}$，这个操作不需要代价。\n\n注意：交换的时候所有左括号的权值是跟着这个括号一起交换的。\n\n你现在想知道的是，将 $s$ 变换为一个不包含你不喜欢的结构的括号序列至少需要多少代价？\n\n## Input\n\n第一行三个整数 $n, x, y$。\n\n第二行一个长度为 $2n$ 的合法括号序列，表示 $s$。\n\n第三行 $n$ 个正整数，其中第 $i$ 个表示左数第 $i$ 个左括号的权值。\n\n## Output\n\n一行一个整数，表示把 $s$ 变换为一个不包含你不喜欢的结构的括号序列至少需要的代价。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n最优方案是先使用操作 2 交换两对括号，然后使用操作 1（此时 $\\texttt{A}$、$\\texttt{B}$、$\\texttt{p}$、$\\texttt{q}$ 都是空串）交换中间的两个括号，代价为 $\\texttt{B}$ 左边那个括号的权值，也就是 $1$。最后得到括号序列 $\\texttt{(())}$，不包含你不喜欢的结构。\n\n**【样例解释 #2】**\n\n最优方案是直接使用操作 1，因为此时计算代价的方式不同了，这次只算 $\\texttt{A}$ 左边的那个括号的权值作为代价。\n\n**【数据范围】**\n\n保证 $2 \\le n \\le 400000$，$0 \\le x, y \\le 1$。\n\n保证所有的权值在 $[1, {10}^7]$ 之内。\n\n| 测试点编号 | 特殊限制 |\n|:-:|:-:|\n| $1 \\sim 3$ | $n \\leq 8$ |\n| $4 \\sim 5$ | 所有权值均相等 |\n| $6 \\sim 8$ | $n \\leq 20$ |\n| $9 \\sim 12$ | $x = 0$，$y = 1$ |\n| $13 \\sim 16$ | $n \\le 2000$ |\n| $17 \\sim 25$ | 无特殊限制 |\n\n**【提示】**\n\n称一个字符串 $s$ 为合法括号序列，当且仅当 $s$ 仅由数量相等的字符 $\\texttt{(}$ 和 $\\texttt{)}$ 组成，且对于 $s$ 的每一个前缀而言，其中 $\\texttt{(}$ 的数量均不少于 $\\texttt{)}$ 的数量。特别地，空串也是合法括号序列。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8293","tags":["贪心","树形数据结构","各省省选","2022","O2优化"],"sample_group":[["2 0 1\n()()\n1 3\n","1\n"],["2 1 0\n()()\n1 3\n","1\n"],["见附件中的 bracket/bracket3.in","见附件中的 bracket/bracket3.ans"]],"created_at":"2026-03-03 11:09:25"}}