题目详情题解（0）讨论（0）提交记录（0）

AT_tupc2023_p.Sub Brackets

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 仅由 ( 和 ) 组成的字符串 SS，现有 MM 个条件，对于每个条件 i (1≤i≤M)i\ (1 \leq i \leq M)，问最多能满足多少个条件。

每个条件 ii ：取出 SS 的第 LiL_i 个字符到第 RiR_i 个字符组成的子串，该子串是一个匹配的括号序列。

这里，匹配的括号序列定义如下：

  • 空字符串；
  • 存在两个非空匹配的括号序列 s,ts, t，将 s,ts, t 依次连接后得到的字符串；
  • 存在匹配的括号序列 ss，则 ( 、ss、) 依次连接得到的字符串。

输入格式

输入通过标准输入给出，格式如下：

N MN\ M
L1 R1L_1\ R_1
L2 R2L_2\ R_2
⋮\vdots
LM RML_M\ R_M

输出格式

输出满足条件的最大个数。

输入输出样例

  • 输入#1

    5 3
1 2
4 5
2 5

    输出#1

    2

  • 输入#2

    2 4
1 2
1 2
1 2
1 2

    输出#2

    4

  • 输入#3

    32 11
25 32
19 32
11 24
20 31
22 25
21 26
17 22
30 31
23 28
4 15
19 22

    输出#3

    8

说明/提示

样例解释 1

当 S=S= (()() 时，第 1 个条件不满足，但第 2、3 个条件满足。
不存在能够同时满足全部 3 个条件的 SS，因此最多能满足 22 个条件。
注意，SS 本身不必是匹配的括号序列。

样例解释 2

条件可能有重复。

数据范围

  • 2≤N≤5002 \leq N \leq 500
  • 1≤M≤5001 \leq M \leq 500
  • 1≤Li<Ri≤N (1≤i≤M)1 \leq L_i < R_i \leq N\ (1 \leq i \leq M)
  • Ri−Li+1R_i - L_i + 1 为偶数
  • 输入均为整数

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页