{"problem":{"name":"[POI 2022/2023 R1] ply","description":{"content":"定义“合法括号串”及其深度如下： - 空串是一个合法括号串，深度为 $0$。 - 如果 $w$ 是一个合法括号串，深度为 $h$，则 $(w)$ 也是一个合法括号串，深度为 $h+1$。 - 如果 $w_1$ 和 $w_2$ 都是合法括号串，深度分别为 $h_1$ 和 $h_2$，则 $w_1w_2$ 也是一个合法括号串，深度为 $\\max(h_1,h_2)$。 定义翻转一个字符为： - 如","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9805"},"statements":[{"statement_type":"Markdown","content":"定义“合法括号串”及其深度如下：\n\n- 空串是一个合法括号串，深度为 $0$。\n- 如果 $w$ 是一个合法括号串，深度为 $h$，则 $(w)$ 也是一个合法括号串，深度为 $h+1$。\n- 如果 $w_1$ 和 $w_2$ 都是合法括号串，深度分别为 $h_1$ 和 $h_2$，则 $w_1w_2$ 也是一个合法括号串，深度为 $\\max(h_1,h_2)$。\n\n定义翻转一个字符为：\n\n- 如果当前字符为 `(`，修改为 `)`。\n- 如果当前字符为 `)`，修改为 `(`。\n\n你需要通过翻转 $s$ 当中某些字符使得深度不超过 $H$，求最小操作次数。\n\n## Input\n\n第一行两个数字 $n \\ (2 \\leq n \\leq 10^6)$ 和 $H \\ (1 \\leq H \\leq \\frac{n}{2})$，分别表示 $|s|$ 和要求修改后不超过的深度。\n\n第二行一个字符串 $s$，表示原来的括号串。\n\n## Output\n\n输出最小修改次数。\n\n[samples]\n\n## Background\n\n题目译自 [POI2022~2023R1 ply](https://sio2.mimuw.edu.pl/c/oi30-1/p/ply/)。\n\n## Note\n\n对于样例，可以修改为 `(()()())`，这样深度为 $2$。\n\n子任务分配如下：\n\n| 子任务编号 | 特殊性质 | 分值 |\n| :-----------: | :-----------: | :-----------: |\n| $1$ | $n \\leq 20$ | $20$ |\n| $2$ | $n \\leq 3000$ | $40$ |\n| $3$ | $n \\leq 10^6$ 且 $H = h-1$ | $20$ |\n| $4$ | $n \\leq 10^6$ | $20$ |\n\n注：$h$ 为输入的括号串的深度。\n\n本题中，子任务 $0$ 为样例。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9805","tags":["POI（波兰）","2022","2023"],"sample_group":[["8 2\n(()(()))","2"]],"created_at":"2026-03-03 11:09:25"}}