Brackets
题目描述
We give the following inductive definition of a “regular brackets” sequence:
- the empty sequence is a regular brackets sequence,
- if
s
is a regular brackets sequence, then(s)
and[s]
are regular brackets sequences, - if
a
andb
are regular brackets sequences, thenab
is a regular brackets sequence, - no other sequence is a regular brackets sequence.
For instance, all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()]
,
while the following character sequences are not:
(, ], )(, ([)], ([(]
.
Given a brackets sequence of characters $a_1a_2 \ldots a_n$, your goal is to find the length of the longest regular brackets sequence that is a subsequence of $s$. That is, you wish to find the largest $m$ such that for indices $i_1, i_2, \ldots, i_m$ where $1 \le i_1 \lt i_2 \lt \cdots \lt i_m \le n$, $a_{i_1}a_{i_2} \ldots a_{i_m}$ is a regular brackets sequence.
Given the initial sequence ([([]])]
, the longest regular brackets subsequence is [([])]
.
题意概述
给定一个只由()[]
这四种字符组成的长度为$n$的字符串,求其最长的满足匹配的子序列的长度。
数据范围:$1 \le n \le 100$。
算法分析
用$f_{i, j}$表示$a_ia_{i+1} \ldots a_j$中满足条件的最大长度。当$j-i \gt 0$时,有如下转移方程
$$
f_{i, j}=
\begin{cases}
\max(f_{i + 1, j - 1} + 2, f_{i, k} + f_{k + 1, j} \mid i \le k \lt j), & a_i \text{ matches } a_j \\
\max(f_{i, k} + f_{k + 1, j} \mid i \le k \lt j), & \text{otherwise}
\end{cases}
$$
考虑边界条件。易知$j-i \le 0$时,$f_{i, j}=0$。
对于$f_{i, j}$,满足$j-i=t$的$f_{i, j}$的值取决于满足$j-i \lt t$的$f_{i, j}$的值。因此可以先从小到大枚举$j-i$,再从小到大枚举$i$,然后从$i$到$j$枚举$k$,利用转移方程解决此题。