poj 1141 括号匹配

2024-08-28 06:38
文章标签 括号 匹配 poj 1141

本文主要是介绍poj 1141 括号匹配,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


根据“黑书”的思路,定义:

d[i][j]为输入序列从下标i到下标j最少需要加多少括号才能成为合法序列。0<=i<=j<len (len为输入序列的长度)。

c[i][j]为输入序列从下标i到下标j的断开位置,如果没有断开则为-1。

i==j时,d[i][j]为1

当s[i]=='(' && s[j]==')' 或者 s[i]=='[' && s[j]==']'时,d[i][j]=d[i+1][j-1]

否则d[i][j]=min{d[i][k]+d[k+1][j]} i<=k<j ,  c[i][j]记录断开的位置k

采用递推方式计算d[i][j]


输出结果时采用递归方式输出print(0, len-1)

输出函数定义为print(int i, int j),表示输出从下标i到下标j的合法序列

当i>j时,直接返回,不需要输出

当i==j时,d[i][j]为1,至少要加一个括号,如果s[i]为'(' 或者')',输出"()",否则输出"[]"

当i>j时,如果c[i][j]>=0,说明从i到j断开了,则递归调用print(i, c[i][j]);和print(c[i][j]+1, j);

                如果c[i][j]<0,说明没有断开,如果s[i]=='(' 则输出'('、 print(i+1, j-1); 和")"

                                                                     否则输出"[" print(i+1, j-1);和"]"


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>using namespace std;
int dp[100][100];
int c[100][100]={-1};
int len;
char s[1000];void cal(){for(int i=0;i<len;i++) dp[i][i]=1;int k,l;for(int i=1;i<len;i++)for(int j=0;j+i<len;j++){l=j+i;int minn=dp[j][j]+dp[j+1][l];c[j][l]=j;for(int k=j+1;k<l;k++){if(dp[j][k]+dp[k+1][l]<minn){minn=dp[j][k]+dp[k+1][l];c[j][l]=k;}}dp[j][l]=minn;if(s[j]=='('&&s[l]==')'||s[j]=='['&&s[l]==']'){if(dp[j+1][l-1]<minn){dp[j][l]=dp[j+1][l-1];c[j][l]=-1;}}}
}void print(int i,int j){if(i>j)return ;if(i==j){if(s[i]=='('||s[j]==')')cout<<"()";elsecout<<"[]";}if(i<j){if(c[i][j]>=0){print(i,c[i][j]);print(c[i][j]+1,j);}else {if(s[i]=='('){cout<<"(";print(i+1,j-1);cout<<")";}else if(s[i]=='['){cout<<"[";print(i+1,j-1);cout<<"]";}}}
}int main(){cin>>s;len=strlen(s);cal();print(0,len-1);puts("");
}


这篇关于poj 1141 括号匹配的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1114012

相关文章

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

浅谈配置MMCV环境,解决报错,版本不匹配问题

《浅谈配置MMCV环境,解决报错,版本不匹配问题》:本文主要介绍浅谈配置MMCV环境,解决报错,版本不匹配问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录配置MMCV环境,解决报错,版本不匹配错误示例正确示例总结配置MMCV环境,解决报错,版本不匹配在col

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

Nginx中location实现多条件匹配的方法详解

《Nginx中location实现多条件匹配的方法详解》在Nginx中,location指令用于匹配请求的URI,虽然location本身是基于单一匹配规则的,但可以通过多种方式实现多个条件的匹配逻辑... 目录1. 概述2. 实现多条件匹配的方式2.1 使用多个 location 块2.2 使用正则表达式

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi