hexo-blog/source/_posts/oi/brackets.md

---

title: Brackets tags:

• Dynamic Programming id: "302" categories:
• - OI
  • Common Skill date: 2017-06-14 20:30:36 ---

题目描述

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 and b are regular brackets sequences, then ab 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 im \le n$, $a{i1}a{i2} \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}$表示$aia{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 } aj \\ \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$，利用转移方程解决此题。