Brackets(区间dp)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8017 | Accepted: 4257 |
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 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 ≤ n, ai1ai2 … 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
Source
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[];
int dp[][];
int main()
{
while(gets(s)!=NULL)
{
if(s[]=='e')break;
memset(dp,,sizeof(dp));
int len=strlen(s);
for(int i=;i<=len;i++)
for(int j=,k=i;k<=len;j++,k++)
{
if(s[j]=='('&&s[k]==')'||s[j]=='['&&s[k]==']')
dp[j][k]=dp[j+][k-]+;
for(int p=j;p<=k;p++)
dp[j][k]=max(dp[j][k],dp[j][p]+dp[p+][k]);
}
printf("%d\n",dp[][len-]);
}
return ;
}
最新文章
- 如何一步一步用DDD设计一个电商网站(九)—— 小心陷入值对象持久化的坑
- 【NopCommerce源码架构学习-一】--初识高性能的开源商城系统cms
- java上传图片或者文件
- 转一篇关于如何在Unity里使用Protobuf
- 06-BCD计数器设计与应用——小梅哥FPGA设计思想与验证方法视频教程配套文档
- hadoop常用管理员命令
- erlang启动参数
- Cannot open your terminal &#39;/dev/pts/4&#39; - please check.
- RollPagerView的用法:
- rowid的作用
- [C++]让CPU使用率曲线呈现为正弦曲线(一)
- .Net Core Identity外面使用Cookie中间件
- bzoj3289
- C#多线程-volatile、lock关键字
- PHP 5.6 中 Automatically populating $HTTP_RAW_POST_DATA is deprecated and will be removed in a future version
- elasticsearch之分词插件使用
- Arm11-mini6410入坑
- EnumUtil 链表转换工具类
- 【转】vue.js表单校验详解
- 2018面向对象程序设计(Java)第4周学习指导及要求