Brackets (区间DP)
个人心得:今天就做了这些区间DP,这一题开始想用最长子序列那些套路的,后面发现不满足无后效性的问题,即(,)的配对
对结果有一定的影响,后面想着就用上一题的思想就慢慢的从小一步一步递增,后面想着越来越大时很多重复,应该要进行分割,
后面想想又不对,就去看题解了,没想到就是分割,还是动手能力太差,还有思维不够。
for(int j=;j+i<ch.size();j++)
{
if(check(j,j+i))
dp[j][j+i]=dp[j+][j+i-]+;
for(int m=j;m<=j+i;m++)
dp[j][j+i]=max(dp[j][j+i],dp[j][m]+dp[m+][j+i]);
}
分割并一次求最大值。动态规划真的是一脸懵逼样,多思考,多瞎想吧,呼~
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<string>
#include<algorithm>
using namespace std;
int money[];
int dp[][];
string ch;
const int inf=;
int check(int i,int j){
if((ch[i]=='('&&ch[j]==')')||(ch[i]=='['&&ch[j]==']'))
return ;
return ;
}
void init(){
for(int i=;i<ch.size();i++)
for(int j=;j<ch.size();j++)
dp[i][j]=;
}
int main(){
int n,m;
while(getline(cin,ch,'\n')){
if(ch=="end") break;
init();
for(int k=;k<ch.size()-;k++)
if(check(k,k+))
dp[k][k+]=;
else
dp[k][k+]=;
for(int i=;i<ch.size();i++)
{
for(int j=;j+i<ch.size();j++)
{
if(check(j,j+i))
dp[j][j+i]=dp[j+][j+i-]+;
for(int m=j;m<=j+i;m++)
dp[j][j+i]=max(dp[j][j+i],dp[j][m]+dp[m+][j+i]);
} }
cout<<dp[][ch.size()-]<<endl;
}
return ;
}
最新文章
- 何谓Restful
- Java设计模式4:单例模式
- django 基于proxy实现用户权限管理
- Day Six(Beta)
- Linux运维初级教程(三)文件及目录权限
- 六个创建模式之单例模式(Singleton Pattern)
- 解决 MySQL Cluster 通过 某一个MySqld节点新建表时,其他 MySqld节点 看不到表内容的问题
- 4.在二元树中找出和为某一值的所有路径[FindPathsInBinaryTree]
- Liunx 下使用cmake
- SegmentFault 2014黑客马拉松 北京 作品demo
- Android EditText的常用技巧
- js时间戳与日期格式之间的互转
- U盘安装,FTP安装CENTOS--错误信息:Unable to read package metadata.This may be due to a missing repodata directory.
- 关于C++中覆盖,重载,隐藏的一点说明
- flex盒子里面元素linehight对高度的影响
- Eclipse常见设置
- easyui合并多个单元格
- Hbase记录-Hbase其他工具
- UE4的AI学习(1)——基本概念
- 【BZOJ】1923 [Sdoi2010]外星千足虫(高斯消元)
热门文章
- 防止基本的XSS攻击 滤掉HTML标签
- sudoers文件设置sudo命令无密码(root密码)登录
- mysql case的语法
- 虚构 css 父级选择器
- linux下安装jsp开发运行环境(centos7)
- IDEA: 遇到问题Error during artifact deployment. See server log for details.详解
- java.lang.NullPointerException报错的几种情况
- springmvc中url-url-pattern /和/*的区别
- inline-block和同级的text-align问题
- EF Code-First 学习之旅 Code First Conventions