`

Brackets Sequence--poj--1141

 
阅读更多

Brackets Sequence

Time Limit: 1000MS

Memory Limit: 65536K

Total Submissions: 11854

Accepted: 3164

Special Judge

Description

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 a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = 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

先读懂题意:

很简单,就是给出一个序列,要求添加最少的符号使其变成题目要求的规则序列。

解题思路:
先用递归的方法来分析问题,设输入序列SiSi+1...Sj最少需要添加d[i,j]个括号,根据不同情况,可以将问题分解为以下子问题:

1S形如(S)或者[S]

只需要把S’变成规则的序列,则S就是规则的了;

2S形如(S

先把S’变成规则序列,接着在最后添加”)”,则S就变成规则序列了;

3S形如S)或者[S’或者S]

和上面的情况类似解法

4)只要序列S的长度大于1,都可以把S分成两部分:Si...SkSk+1...Sj,然后分别将子序列变成规则序列,则拼接在一起的S就是规则序列了。

下面给出递归的伪代码:

function Bracket(i, j : Integer); //ij是本序列在原始输入序列中的开始和结束下标

begin

if i>j then return 0

else if i=j then return 1;

else begin

Answer := MAX;

if s[i]s[j]='()' or s[i]s[j]='[]' then //对应上面情形1

Answer := min(Answer, Bracket(i+1, j-1));

if s[i]='(' or s[i]='[' then //对应上面情形2/3

Answer := min(Answer, Bracket(i+1, j) + 1); //1表示在右边加了')'']'

if s[j]=')' or s[j]=']' then //同上2/3

Answer := min(Answer, Bracker(i, j-1)+1);

For k:=i to j-1 do //对应上面情形4

Answer := min(Answer, Bracket(i, k) + Bracket(k+1, j));

end;

end;

上面递归的算法效率很低(递归进行了很多重复计算),时间复杂度是指数级的,因此我们必须在递归的基础上进行改进,即采用动态规划。

一、记忆化搜索

在每次调用Bracket函数之前,先检查之前是否已经计算过这个值了,如果是则直接从之前保存的表中找出:

function Bracket(i , j : Integer);

begin

if Calculated[i, j] then return d[i, j];

//此处插入上面的递归代码

d[i, j] := Answer

Calculated[i, j] := true;

end;

二、自底向上的递推法

由于计算d[i, j]之前需要知道d[i+1, j]d[i, j-1]d[i+1, j-1]的值,所以按照j-i递增的顺序计算出d[i, j]

for i:=1 to n do d[i, i-1]:=0; //置初始值

for i:=1 to n do d[i, i]:=1;

for p:=1 to n-1 do

for i:=1 to n-p do

begin

j:=i+p

d[i, j]:=MAX;

if s[i]s[j]='()' or s[i]s[j]='[]' then

d[i, j] := min(d[i, j], d[i+1, j-1]);

if s[i]='(' or s[i]='[' then

d[i, j] :=min(d[i, j], d[i+1, j] + 1);

if s[j]=')' or s[j]=']' then

d[i, j] := min(d[i, j], d[i, j-1]+1);

For k:=i to j-1 do

d[i, j] := min(d[i, j], d[i, k] + d[k+1, j]);

end;

AC代码如下:

#include <iostream>

#include <string>

const int MAX = 1000;

int flag[MAX][MAX]; //in[i]in[j]间字符数

int mem[MAX][MAX]; //mem[i][j]记录in[i]in[j]之间的序列是否需要分成两部分

std::string in;//存储输入的字符串

int min(int x, int y)

{

return (x>y ? y : x);

}

//打印出结果字符

void find(int xx, int yy)

{

if(xx > yy)

return;

if(mem[xx][yy] == -1) //当前序列不需要分成两部分

{

if(xx == yy)//当前序列只剩一个字符

{

if(in[xx] =='(' || in[xx] == ')')

std::cout<<"()";

else if(in[xx]=='[' || in[xx]== ']')

std::cout<<"[]";

}

else //当前序列不止一个字符

{

std::cout<<in[xx]; //输出当前序列第一个字符

find(xx+1, yy-1); //对中间的部分递归

std::cout<<in[yy]; //输出当前序列最后一个字符

}

}

else //当前序列需要分成两部分

{

int tmp = mem[xx][yy]; //分割的下标

find(xx, tmp);

find(tmp+1, yy);

}

return;

}

int main()

{

std::cin>>in;

int len = in.length();

memset(flag, 0, sizeof(flag));

memset(mem, -1, sizeof(mem));

for(int k=0; k<len; k++)

{

for(int i=0, j=k; j<len; i++, j++)

{

if(i == j)

flag[i][j] = 1; //记录in[i]in[j]中间字符的个数

else

{

int tmp = 10000000;

if((in[i]=='(' && in[j]==')') ||

(in[i]=='[' && in[j]==']'))

{

tmp = min(tmp, flag[i+1][j-1]);

}

//只要当前序列S的长度大于1,都可以把S分成两部分:Si...SkSk+1(下标)...Sj

//然后分别将子序列变成规则序列,则拼接在一起的就是规则序列了

for(int t=i; t<j; t++)

{

if(tmp>flag[i][t] + flag[t+1][j])//找出字符数最小值

{

tmp = flag[i][t] + flag[t+1][j];

mem[i][j] = t; //记录分割的下标t

}

}

flag[i][j] = tmp;//in[i]in[j]间字符数为tmp

}

}

}

find(0, len-1);

std::cout<<std::endl;

system("pause");

return 0;

}

分享到:
评论

相关推荐

    asp代码ASP家教信息管理系统(源代码+论文)

    asp代码ASP家教信息管理系统(源代码+论文)本资源系百度网盘分享地址

    基于ssm高校毕业选题管理系统.zip

    基于ssm高校毕业选题管理系统.zip

    基于旷视研究院领先的深度学习算法,提供满足多业务场景的预训练模型.zip

    人工智能毕业设计&课程设计

    tensorflow_model_optimization-0.1.3.dev0-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    tensorflow_model_analysis-0.15.0-py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    粒子群算法.docx 粒子群算法(Particle Swarm Optimization,PSO)是一种优化算法,受到鸟群或鱼

    粒子群算法 粒子群算法(Particle Swarm Optimization,PSO)是一种优化算法,受到鸟群或鱼群等群体行为的启发。该算法通过模拟群体中个体之间的合作和竞争来搜索最优解。粒子群算法通常用于解决连续优化问题。 ### 工作原理: 1. **初始化**:随机生成一群粒子(也称为个体),每个粒子代表搜索空间中的一个解,并随机初始化其位置和速度。 2. **评估**:根据每个粒子的位置,计算其对应的适应度值(目标函数值)。 3. **更新**:根据个体最优和全局最优的情况,更新每个粒子的速度和位置。粒子会根据自己历史最好的位置以及整个群体历史最好的位置进行调整,以期望更好的搜索方向。 4. **迭代**:重复评估和更新步骤,直到满足停止条件(如达到最大迭代次数、目标函数值足够接近最优解等)。 ### 主要参数: - 粒子数量(Population Size):群体中粒子的数量,通常越大越容易找到全局最优解,但计算成本也会增加。 - 惯性权重(Inertia Weight):控制粒子运动的惯性,平衡局部搜索和全局搜索能力。通常随着迭代次数增加而逐渐减小。

    20210327 AI-for-Drug-Discovery-2020.pdf

    20210327 AI-for-Drug-Discovery-2020

    tensorflow_model_optimization-0.1.2-py2.py3-none-any.whl

    Python库是一组预先编写的代码模块,旨在帮助开发者实现特定的编程任务,无需从零开始编写代码。这些库可以包括各种功能,如数学运算、文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。

    Linux创建虚拟机的步骤

    Linux创建虚拟机的步骤

    基于SpringBoot的校园二手书交易管理系统设计源码

    这是一个基于SpringBoot开发的校园二手书交易管理系统,使用Java语言,包含102个文件。主要文件类型包括39个Java源文件、23个HTML文件、10个PNG图片文件、9个XML文件、9个JavaScript文件、4个CSS文件、2个Markdown文档、2个JPG图片文件、1个gitignore文件和1个SVG文件。该项目简洁易用,采用的技术经典,非常适合Java项目入门学习和企业级Java开发熟悉,提供了二手书交易管理、用户认证、数据统计等功能,旨在为校园内的二手书交易提供一个便捷、安全的平台。

    基于SSM的旅游管理系统.zip

    基于SSM的旅游管理系统.zip

    基于ssm框架网络财务设计与实现.zip

    基于ssm框架网络财务设计与实现.zip

    三菱PLC例程源码PLC同变频器通讯程序3

    三菱PLC例程源码PLC同变频器通讯程序3本资源系百度网盘分享地址

    基于ssm+jsp网上茶叶销售平台.zip

    基于ssm+jsp网上茶叶销售平台.zip

    通信专业毕业设计(论文)-企业网通信方案设计

    随着网络和科学技术的飞速发展,网络建设作为信息化建设的基础,也越来越受到企业的重视,网络结构和网络信息安全都是企业信息化建设中需要解决的重要问题。 本设计出于对众宇通讯公司长期稳定发展的考虑,针对公司的现状和发展需求,为公司设计了一个稳定的、相对安全的、可扩展并且可以支撑必要的网络应用的网络结构。在此次设计中,主要的运用到的技术与实现功能有:(1)汇聚交换机上使用DHCP技术,使各个接入层设备可自动获取相应的IP地址,也避免了IP地址的冲突;(2)运用VRRP技术,增强网络的连续性和稳定性,实现多链路备份冗余和网关备份冗余;(3)运用MSTP技术,将不同的VLAN与相应实例捆绑,避免了网络环路和广播风暴的产生;(4)通过防火墙技术,实现了企业内部与外部网络之间的信息交互安全。除此之外,还进行了VLAN的划分,端口安全设置,ACL访问限制,NAT地址转换,使用OSPF协议、静态路由等网络配置。 本论文基于华为ENSP仿真模拟软件,充分考虑到了整个公司网络今后的实用性、安全性以及可扩展性。利用所学的相关知识和网络技术,对众宇通讯公司的网络进行模拟设计。此设计根据三层网络结构来搭建网络拓扑,

    Gromacs中文手册5.0.2.pdf

    Gromacs中文手册5.0.2

    三菱PLC例程源码八层以下货梯通用程序(奥菱达)

    三菱PLC例程源码八层以下货梯通用程序(奥菱达)本资源系百度网盘分享地址

    seg.v

    seg.v

    ftqqzx.zip

    ftqqzx.zip

    基于tensorflow深度学习的中文机器阅读理解-完形填空.zip

    人工智能毕业设计&课程设计

Global site tag (gtag.js) - Google Analytics