POJ 2955 Brackets (区间dp 括号匹配)

2024-03-20 14:08

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


Brackets
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3951 Accepted: 2078

Description

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, and
  • 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 a1a2an, 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 i1, i2, …, im where 1 ≤ i1 < i2 < … < im n, ai1ai2aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

Source

Stanford Local 2004

题目链接:http://poj.org/problem?id=2955

题目大意:给一个括号序列,问序列中合法的括号最多有多少个,若A合法,则[A],(A)均合法,若A,B合法则AB也合法

题目分析:和POJ 1141那道经典括号匹配类似,这题更简单一些,想办法把问题转化,既然要求最大的括号匹配数,我们考虑加最少的括号,使得整个序列合法,这样就转变成1141那题,开下脑动类比二分图最大匹配的性质,最大匹配+最大独立集=点数,显然要加入最少的点使序列合法,则加的最少的点数即为|最大独立集|,我们要求的是原序列的|最大匹配|,以上纯属yy,下面给出转移方程,和1141一模一样
dp[i][i] = 1;
然后枚举区间长度
1)外围匹配:dp[i][j] = dp[i + 1][j - 1];
2)外围不匹配,枚举分割点:dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); (i <= k < j)


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 0x3fffffff;
char s[205];
int dp[205][205];int main()
{while(scanf("%s", s) != EOF && strcmp(s, "end") != 0){int len = strlen(s);memset(dp, 0, sizeof(dp));for(int i = 0; i < len; i++)dp[i][i] = 1;for(int l = 1; l < len; l++){for(int i = 0; i < len - l; i++){int j = i + l;dp[i][j] = INF;if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))dp[i][j] = dp[i + 1][j - 1];for(int k = i; k < j; k++)dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);}}printf("%d\n", len - dp[0][len - 1]);}
}


这篇关于POJ 2955 Brackets (区间dp 括号匹配)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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路由

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上