[LMXOI Round 1] Placer

Luogu

IDLGP10115

Time1000ms

Memory512MB

DifficultyP4

动态规划 DP枚举

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)$ 之和。求美丽度最大为多少。 ## Input 第一行一个整数 $n$。第二行一个字符串，代表括号序列。第三行代表序列 $a$。 ## Output 第一行一个整数，表示最大的美丽度。 [samples] ## Background LMX 最近迷上了括号序列，她尤其钟爱合法括号序列。 LMX 为了检验 HQZ 的真诚，于是她出一道题准备考验下 HQZ。 ## Note **样例解释 #1** 原串可以划分成三个区间：$[1,2],[3,3],[4,5]$。贡献为 $(a_2-a_1)+0+(a_5-a_4)=(3-1)+0+(5-3)=4$ | 子任务编号 | $n$ | 特殊性质 | 分值 | | :--------: | :--------: | :-------------: | :--: | | Subtask #1 | $\le 5000$ | 无 | $30$ | | Subtask #2 | $\le 10 ^ 5$ | 无 | $20$ | | Subtask #3 | $\le 3 \times 10 ^ 6$ | 括号序列为 $()()\dots()$ | $15$ | | Subtask #4 | $\le 3 \times 10 ^ 6$ | 无 | $35$ | 对于 $100\%$ 的数据，$1\le a_i \le 10^9$。

Samples

Input #1

5
()(()
1 3 2 3 5

Output #1

Input #2

10
()((())())
2 4 1 7 3 2 8 4 9 5

Output #2

API Response (JSON)

{
  "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求美丽度...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments