[海淀区普及组 2025 T2] 括号构造大赛

Luogu

IDLGB4454

Time2000ms

Memory512MB

DifficultyP3

动态规划 DP2025北京初中活动

元旦联欢会上，老师为信息学社团的同学举办了构造大赛，由老师给出两个括号序列，看谁能最快构造出最短的满足要求的括号序列，具体规则如下：对于两个字符串 $A$、$B$，若字符串 $B$ 是 $A$ 的一个子序列（不要求连续），则称 $A$ 包含了 $B$。给出两个只由 `(` 和 `)` 组成的括号串 $S$、$T$。你需要构造一个字符串 $f$，要求同时满足： 1. 字符串 $f$ 包含 $S$； 2. 字符串 $f$ 包含 $T$； 3. $f$ 是一个合法括号串。构造大赛要求学生写出一种 $f$ 的具体方案，但为了方便，你只需要求出满足上述条件的字符串 $f$ 的最短长度即可。其中，合法括号串定义如下： 1. `()` 是合法括号串； 2. 若 $A$ 是合法括号串，则 $(A)$ 也是合法括号串； 3. 若 $A$ 和 $B$ 都是合法括号串，则 $AB$ 也是合法括号串。 ## Input 第一行输入一个字符串 $S$（$1 \leq |S| \leq 200$）。第二行输入一个字符串 $T$（$1 \leq |T| \leq 200$）。 ## Output 一个正整数，表示最短的包含 $S$、$T$ 的括号序列长度。 [samples] ## Note 样例 1 解释：合法的序列可以是 `(())()()` 数据范围：对于前 30% 的数据，满足输入的括号串长度分别不超过10。对于另外 30% 数据，满足输入的 $S$ 串长度等于 1。对于所有数据，满足“输入格式”中给出的数据范围。

Samples

Input #1

(())(()
()))()

Output #1

Input #2

)
((

Output #2

Input #3

)
)))

Output #3

Input #4

())
(()(()(()(

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[海淀区普及组 2025 T2] 括号构造大赛",
    "description": {
      "content": "元旦联欢会上，老师为信息学社团的同学举办了构造大赛，由老师给出两个括号序列，看谁能最快构造出最短的满足要求的括号序列，具体规则如下：对于两个字符串 $A$、$B$，若字符串 $B$ 是 $A$ 的一个子序列（不要求连续），则称 $A$ 包含了 $B$。 给出两个只由 `(` 和 `)` 组成的括号串 $S$、$T$。你需要构造一个字符串 $f$，要求同时满足： 1. 字符串 $f$ 包含 $S$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4454"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "元旦联欢会上，老师为信息学社团的同学举办了构造大赛，由老师给出两个括号序列，看谁能最快构造出最短的满足要求的括号序列，具体规则如下：对于两个字符串 $A$、$B$，若字符串 $B$ 是 $A$ 的一个子序列（不要求连续），则称 $A$ 包含了 $B$。\n\n给出两个只由 `(` 和 `)` 组成的括号串 $S$、$T$。你需要构造一个字符串 $f$，要求同时满足：\n1. 字符串 $f$ 包含 $S$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments