「WHOI-1」ymh 是 AK 哥！！！

Luogu

IDLGP8355

Time1000ms

Memory256MB

DifficultyP1

字符串O2优化

给你一个括号串 $s$。定义一次操作是交换他们当中相邻的两个字符。你的任务是找出若干次操作后 $s$ 的括号匹配前缀长度最大值。 ## Input 一行一个正整数 $n$ 表示字符串长度。接下来一行一个字符串表示 $s$。 ## Output 一行一个自然数表示答案。 [samples] ## Background $2077$ 年春。$15$ 岁的 miku 正在对着你谷发呆，突然看到一个奇怪的问题，你能帮帮他么？？ ---- 你要先学会一些定义。我们约定一个字符串下标从 $1$ 开始，$s[l,r]$ 表示 $s_ls_{l+1}\dots s_r$ 拼接成的一个字符串。 --- 定义括号匹配串如下： - 空串是括号匹配串。 - 如果 $A$ 是括号匹配串，则 $(A)$ 是括号匹配串。 - 如果 $A,B$ 是括号匹配串，则 $AB$ 是括号匹配串。 --- 括号匹配前缀长度是指最大的 $k$ 使得 $s[1,k]$ 是一个括号匹配串。比如： - $s=\text{(())(()}$ 时括号匹配前缀长度是 $4$。 - $s=\text{()()()(()))(}$ 时括号匹配前缀长度是 $10$。 ## Note **本题采用 $\texttt{Subtask}$ 计分方式，只有通过该 $\texttt{Subtask}$ 的所有测试点才能得到该点的分数。** | $\texttt{Subtask}$ 编号 | 特殊限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | 只含左括号或只含右括号 | 2 | | 2 | $n \leq 2$ | 3 | | 3 | $n \leq 10$ | 10 | | 4 | $n \leq 1000$ | 20 | | 5 | 无| 65 | 对于 $100\%$ 的数据，保证 $ 1\leq n\leq10^6$。

Samples

Input #1

3
(()

Output #1

Input #2

2
()

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「WHOI-1」ymh  是 AK 哥！！！",
    "description": {
      "content": "给你一个括号串 $s$。定义一次操作是交换他们当中相邻的两个字符。 你的任务是找出若干次操作后 $s$ 的括号匹配前缀长度最大值。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8355"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个括号串 $s$。定义一次操作是交换他们当中相邻的两个字符。\n\n你的任务是找出若干次操作后 $s$ 的括号匹配前缀长度最大值。\n\n## Input\n\n一行一个正整数 $n$ 表示字符串长度。\n\n接下来一行一个字符串表示 $s$。\n\n## Output\n\n一行一个自然数表示答案。\n\n[samples]\n\n## Background\n\n$2077$ 年春。$15$ 岁的 miku 正在对着你谷发...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments