Brackets(括号匹配,区间dp)_we give the following inductive definition of a “r-程序员宅基地

技术标签: 区间dp  

https://cn.vjudge.net/problem/POJ-2955

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 a1a2 … an, 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 ≤ nai1ai2 … aim 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

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
char s[105];
int dp[105][105];
int f(char a,char b){
	if(a=='('&&b==')') return 1;
	if(a=='['&&b==']') return 1;
	return 0;
}
int dfs(int l,int r){
	if(dp[l][r]!=-1) return dp[l][r];
	if(l==r) return dp[l][r]=0;
	if(l+1==r) return dp[l][r]=f(s[l],s[r]);
    int ans=f(s[l],s[r]);
    if(ans) ans+=dfs(l+1,r-1);
    for(int i=l;i<r;i++){//注意是从l开始枚举
    	ans=max(ans,dfs(l,i)+dfs(i+1,r));
	}
	return dp[l][r]=ans;
}
int main(){
    while(~scanf("%s",s+1)){
    	if(s[1]=='e') break;
    	int len=strlen(s+1);
    	memset(dp,-1,sizeof(dp));
    	printf("%d\n",2*dfs(1,len));
	}
	return 0;
}


 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_42936517/article/details/96387010

智能推荐

单例模式为什么需要volatile关键字?_单例为什么要volitole-程序员宅基地

文章浏览阅读1.1k次。在单例模式中,为了保证效率的同时,保证线程安全,我们会了解这一段代码双重校验锁public class SingletonLazy { private volatile static SingletonLazy data; private SingletonLazy(){ System.out.println("初始化"); } public SingletonLazy getData() { if (data == null) { _单例为什么要volitole

用websocket实现文件传输 nodejs_nodejs 可以通过websocket 推送文件流吗-程序员宅基地

文章浏览阅读4.6k次,点赞2次,收藏5次。  学校的大作业,要用套接字写一个有文件传输功能的系统,js用的最多,于是首先想到了用nodejs来实现,所以用html5的websocket来写了一个最小实现网盘 有基本的上传 新建 下载文件的功能。实现思路  里面的所有操作都是在websocket连接上的,比如文件列表是nodesj先遍历当前文件夹,返回包含了文件属性的json格式,前端根据这个文件对象列表进行渲染。  然后每个显示文件..._nodejs 可以通过websocket 推送文件流吗

软件开发传统模型——瀑布模型、原型模型、增量模型、螺旋模型、喷泉模型_软件开发 增量模型-程序员宅基地

文章浏览阅读263次。软件开发传统模型——瀑布模型、原型模型、增量模型、螺旋模型、喷泉模型_软件开发模型_言己日记的博客-程序员宅基地_软件开发 增量模型

css3 dyoe_css怎么让图案上下浮动-程序员宅基地

文章浏览阅读540次。在css中,可以使用animation属性和@keyframes规则给img图片元素设置上下浮动动画效果来让图案上下浮动;动画的快慢速度可以通过元素高度与animation中的秒数去调整。本教程操作环境:Windows7系统、HTML5&&CSS3版本,Dell G3电脑。css3实现一个上下浮动的动画效果(animation)CSS@keyframes movepoint {25..._dyoe

ext6如何获得table选择的行数据_ext js6 中获取所选行的数据-程序员宅基地

文章浏览阅读1k次。Ext.define('Admin.view.system.RoleSerachAdd', { extend : 'Ext.window.Window', xtype : 'RoleSerachAdd', controller : 'roleserachadd', height : 500, width : 400, layout : 'fit', plain : true, re_ext js6 中获取所选行的数据

视频教程-HTML+CSS+JavaScript基础-HTML5/CSS-程序员宅基地

文章浏览阅读1.1k次。HTML+CSS+JavaScript基础 本系列课程由多位老师共同录制而成..._html+css+jss视频教程

随便推点

一步一步写嵌入式操作系统 第二章练习。_如何在entity-manager程序下的configuartion文件夹下进行添加我们所支持的单板-程序员宅基地

文章浏览阅读2.2k次。完成《一步一步写嵌入式操作系统》一书中的第二章练习,注意Ubuntu 11.10上通过apt-get install skyeye所安装的skyeye是1.2.5,无法实现书中所说的输出到控制台的结果。需要自己安装skyeye 1.2.6, 到skyeye官网上下载skyeye 1.2.6,解压,然后make, make install如其它网友提到,ubuntu上安装1.2.6时需要修改devi_如何在entity-manager程序下的configuartion文件夹下进行添加我们所支持的单板的j

spark2原理分析-BlockManager总体架构设计-程序员宅基地

文章浏览阅读283次。概述本文介绍spark的存储体系,通过本文的学习可以对spark的BlockManager体系有一个总体的把握。BlockManger的总体架构BlockManager运行在spark的每个节点上(包括driver和executors),它提供了一个保存和获取本地或远端数据块到内存、磁盘、或off-heap中的统一接口。从该架构图可见,在spark的每个任务执行器中都有一个blockma...

Dubbo——Dubbo中的常用标签、服务化最佳实践_dubbo标签-程序员宅基地

文章浏览阅读7.5k次,点赞3次,收藏5次。1.Dubbo中的常用标签Dubbo 中常用标签。分为三个类别:公用标签,服务提供者标签,服务消费者标签。_dubbo标签

ExtJS的使用方法汇总6——工具栏和菜单_extjs window 添加菜单栏-程序员宅基地

文章浏览阅读867次。菜单的种类很多,包括下拉菜单、分组菜单、右键菜单等等,右键菜单与Window桌面上单击右键弹出的菜单效果一样,只是样式不同,菜单上的内容包括文字、单选框、按钮等。对于EXT来说,这些菜单的实现都非常简单。我们可以在一个面板的顶端或底端放置一横排功能按钮,按下不同的按钮时会执行不同的操作。我们把这个横条称为工具条,放在工具条上的按钮称为菜单。本章将详细介绍EXT中工具栏和菜单的使用方法。一、_extjs window 添加菜单栏

十大经典排序算法-程序员宅基地

文章浏览阅读239次。排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括:关于时间复杂度:平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和...

Unity3D Find不存在的gameObject_对那些不存在的路径gameobject.find会崩溃-程序员宅基地

文章浏览阅读1.9k次。项目中有一些功能会去Find一些不存在的GameObject,这是Unity会报错,如果不想被错误影响让程序继续运行下去,有两种方法可行。1.最简单的,用c#的try catch,捕获异常并处理。2.利用transform.childCountd得到子节点数量,之后用循环遍历所有子节点,通过transform.GetChild得到具体的子节点,并通过名字来找到想要查找的子节点,但这中方法在_对那些不存在的路径gameobject.find会崩溃