版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: "题解 - [POJ 1141] [ZOJ 1463] [UVa 1626] [Ural 1183] Brackets Sequence" categories:

题目链接

<!-- more -->

原始题面

Let us define a regular brackets sequence in the following way:

  1. Empty sequence is a regular sequence
  2. If S is a regular sequence, then (S) and [S] are both regular sequences
  3. If A and B are regular sequences, then AB is a regular sequence

For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string $a_1~a_2~...~a_n$ is called a subsequence of the string $b_1~b_2~...~b_m$, if there exist such indices $1 = i_1 < i_2 < ... < i_n = m$, that $aj = b{i_j}$ for all $1 \leqslant j \leqslant n$

Input

The input file contains at most $100$ brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them

Output

Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence

Sample Input

([(]

Sample Output

()[()]

Source

Northeastern Europe 2001

题意简述

对一个字符串, 按如下规则定义合法的括号序列:

  1. 空字符串为合法的括号序列
  2. 若A为合法的括号序列, 则(A), [A]也为合法的括号序列
  3. 若A, B为合法的括号序列, 则AB也为合法的括号序列

给出由(, ), [, ]构成的字符串, 添加尽量少的(, ), [, ]使其变为合法的括号序列, 并输出结果

解题思路

一道区间类 DP 题, 我们这样考虑状态转移方程

记给定字符串 $s$, $si$ 为其第 $i$ 位的字符, $s{i\to j}$ 为其第 $i$ 位第 $j$ 位构成的子串

设 $f(i,j)$ 为: 使 $s_{i\to j}$ 合法化所需插入的最少字符数

我们很容易能发现几个特例

  1. 如果 $i>j$, 子串不存在, 自然有 $f(i,j)=0$
  2. 如果 $i=j$, 那么其必定需要最少需要 $1$ 个字符完成合法化
  3. 如果 $s_i$ 和 $s_j$ 能够配对的话, $f(i,j)=f(i+1,j-1)$

而一般情况下的 $f(i,j)$, 我们可以将其拆分成两个子串分别计算再求和, 从而可以得出

$$ f(i,j)=\min_{i\leqslant k\leqslant j}{f(i,k)+f(k+1,j)} $$

总结一下就是

$$ f(i,j)=\begin{cases} 0,&i>j\ 1,&i=j\ f(i+1,j-1),&s_i, sj~\text{are}~\text{matched}\ \displaystyle\min{i\leqslant k< j}{f(i,k)+f(k+1,j)},&\text{otherwise} \end{cases} $$

由于用循环来实现比较困难, 所以这里选用记忆化搜索的方式来实现

本题要求的不是输出 $f(1,len_s)$ 而是合法化后的字符串, 所以我们要根据状态转移方程来做些许改造

  1. 如果 $i>j$, 子串不存在, 合法化后的字符串自然也不存在, 所以什么也不需要做
  2. 如果 $i=j$, 那么其必定需要最少需要 $1$ 个字符完成合法化, 直接匹配并输出即可
  3. 如果 $s_i$ 和 $sj$ 能够配对的话, 用两边的字符把 $s{i+1\to j-1}$ 合法化的字符串夹在中间, 并输出
  4. 一般情况下, 如果 $f(i,j)=f(i,k)+f(k+1,j)$, 那么直接将 $s{i\to k}$ 和 $s{k+1\to j}$ 合法化的字符串拼接起来并输出即可

代码

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:POJ_1141 POJ/1141/0.cpp %} </details>