1497 . 害羞的括號

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Enzo

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (2/2)

Tags

ytp ytp2026 ytp-junior

Description

小括號很可愛，有超級多個左小括號 ( 和右小括號 ) 要玩遊戲。

地上從左到右有 $N$ 個格子排成一列，編號為 $1$ 到 $N$。這些小括號想試著用不同的方式佔領格子。

格子分成兩種，一種只能由左小括號佔領，另一種只能交給右小括號。他們已經調查好每個格子的種類了。

小括號很害羞，需要維持足夠的社交距離，所以考慮任意兩個佔領格子的小括號，他們的格子編號必須至少相差 $D$ 以上。

另外因為天生的限制，這些佔領格子的小括號必須組成一個完整的合法括號序列。也就是按照這些小括號的順序，可以在中間插入一些 1 和 + 符號，使得整個式子在數學上有能算出來的值。

他們想知道，遵守以上規則並妥善安排的話，最多可以佔領多少個格子。

Input Format

輸入有兩行，第一行是兩個以空白隔開的正整數 $N,D$。

接下來有一行長度為 $N$ 的字串，每個字元都是小括號 ( 或 )，第 $i$ 個字元代表編號為 $i$ 的格子能被哪種小括號佔領。

  • $1 \leq D \leq N \leq 5000$

Output Format

輸出一行一個整數，代表最多可以佔領多少個格子。

Sample Input 1

6 1
()(()(

Sample Output 1

4

Sample Input 2

20 3
())()))))(()))))(())

Sample Output 2

6

Sample Input 3

20 20
))()(()(()((()))(())

Sample Output 3

0

Sample Input 4

1 1
(

Sample Output 4

0

Hints

範測 1 解釋：

有以下 2 種佔領方式都能達到佔領最多格子：
- 佔領第 1, 2, 3 和第 5 個格子
- 佔領第 1, 2, 4 和第 5 個格子

範測 2 解釋：佔領第 1, 4, 7, 10, 15, 20 個格子，是其中一種達到佔領最多格子的方式。

在範測 3 和 4 裡面，沒有辦法佔領任何格子。

Problem Source

2026 YTP 國中組決賽 p9

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測試資料 0
2 4~23 $D=1$ 7
3 0~3, 24~48 $N \leq 300$ 6
4 0~63 無額外限制 7

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 3 4
1 1000 1048576 65536 1 3 4
2 1000 1048576 65536 1 3 4
3 1000 1048576 65536 1 3 4
4 1000 1048576 65536 2 4
5 1000 1048576 65536 2 4
6 1000 1048576 65536 2 4
7 1000 1048576 65536 2 4
8 1000 1048576 65536 2 4
9 1000 1048576 65536 2 4
10 1000 1048576 65536 2 4
11 1000 1048576 65536 2 4
12 1000 1048576 65536 2 4
13 1000 1048576 65536 2 4
14 1000 1048576 65536 2 4
15 1000 1048576 65536 2 4
16 1000 1048576 65536 2 4
17 1000 1048576 65536 2 4
18 1000 1048576 65536 2 4
19 1000 1048576 65536 2 4
20 1000 1048576 65536 2 4
21 1000 1048576 65536 2 4
22 1000 1048576 65536 2 4
23 1000 1048576 65536 2 4
24 1000 1048576 65536 3 4
25 1000 1048576 65536 3 4
26 1000 1048576 65536 3 4
27 1000 1048576 65536 3 4
28 1000 1048576 65536 3 4
29 1000 1048576 65536 3 4
30 1000 1048576 65536 3 4
31 1000 1048576 65536 3 4
32 1000 1048576 65536 3 4
33 1000 1048576 65536 3 4
34 1000 1048576 65536 3 4
35 1000 1048576 65536 3 4
36 1000 1048576 65536 3 4
37 1000 1048576 65536 3 4
38 1000 1048576 65536 3 4
39 1000 1048576 65536 3 4
40 1000 1048576 65536 3 4
41 1000 1048576 65536 3 4
42 1000 1048576 65536 3 4
43 1000 1048576 65536 3 4
44 1000 1048576 65536 3 4
45 1000 1048576 65536 3 4
46 1000 1048576 65536 3 4
47 1000 1048576 65536 3 4
48 1000 1048576 65536 3 4
49 1000 1048576 65536 4
50 1000 1048576 65536 4
51 1000 1048576 65536 4
52 1000 1048576 65536 4
53 1000 1048576 65536 4
54 1000 1048576 65536 4
55 1000 1048576 65536 4
56 1000 1048576 65536 4
57 1000 1048576 65536 4
58 1000 1048576 65536 4
59 1000 1048576 65536 4
60 1000 1048576 65536 4
61 1000 1048576 65536 4
62 1000 1048576 65536 4
63 1000 1048576 65536 4
Submit
Back to Top