{"problem":{"name":"[LMXOI Round 1] Placer","description":{"content":"LMX 给出了一个长度为 $n$ 括号序列 $S$，以及一个长度为 $n$ 的序列 $a_i$。 定义 $w(l,r)= \\begin{cases} a_r-a_l, & S_{l..r} \\text{为合法括号序列}\\\\ \\ 0 & \\text{otherwise} \\end{cases}$ 你可以将序列分成若干非空子段，定义整个序列的美丽度为每段的 $w(l , r)$ 之和。 求美丽度","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10115"},"statements":[{"statement_type":"Markdown","content":"LMX 给出了一个长度为 $n$ 括号序列 $S$，以及一个长度为 $n$ 的序列 $a_i$。\n\n定义 $w(l,r)=\n\\begin{cases}\na_r-a_l, & S_{l..r} \\text{为合法括号序列}\\\\\n\\ 0 & \\text{otherwise}\n\\end{cases}$\n\n你可以将序列分成若干非空子段，定义整个序列的美丽度为每段的 $w(l , r)$ 之和。\n\n求美丽度最大为多少。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行一个字符串，代表括号序列。\n\n第三行代表序列 $a$。\n\n## Output\n\n第一行一个整数，表示最大的美丽度。\n\n[samples]\n\n## Background\n\nLMX 最近迷上了括号序列，她尤其钟爱合法括号序列。\n\nLMX 为了检验 HQZ 的真诚，于是她出一道题准备考验下 HQZ。\n\n## Note\n\n**样例解释 #1**\n\n原串可以划分成三个区间：$[1,2],[3,3],[4,5]$。贡献为 $(a_2-a_1)+0+(a_5-a_4)=(3-1)+0+(5-3)=4$\n\n| 子任务编号 | $n$ | 特殊性质 | 分值 |\n| :--------: | :--------: | :-------------: | :--: |\n| Subtask #1 | $\\le 5000$ | 无 | $30$ |\n| Subtask #2 | $\\le 10 ^ 5$ | 无 | $20$ |\n| Subtask #3 | $\\le 3 \\times 10 ^ 6$ | 括号序列为 $()()\\dots()$ | $15$ |\n| Subtask #4 | $\\le 3 \\times 10 ^ 6$ | 无 | $35$ |\n\n对于 $100\\%$ 的数据，$1\\le a_i \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10115","tags":["动态规划 DP","枚举"],"sample_group":[["5\n()(()\n1 3 2 3 5","4"],["10\n()((())())\n2 4 1 7 3 2 8 4 9 5","8"]],"created_at":"2026-03-03 11:09:25"}}