题目大概说给一个长m的括号序列s,要在其前面和后面添加括号使其变为合法的长度n的括号序列,p+s+q,问有几种方式。(合法的括号序列当且仅当左括号总数等于右括号总数且任何一个前缀左括号数大于等于右括号数)
我这么想的:n-m<=2000,因而可以dp计算p和q的方案数,同时在各个地方加入s进行转移。
- dp[0/1][i][j]表示s没有/有加入时,p和q前i个括号已经确定且还有j的左括号还没匹配的方案数
- 注意到任何前缀的左括号都是大于等于右括号的,因此j这一维不会小于0。
- 那么转移,我用我为人人转移,就是:
- 尾巴加上左括号:
d[0][i+1][j+1]+=d[0][i][j]
- 尾巴加上右括号:
d[0][i+1][j-1]+=d[0][i][j]
- 尾巴加上左括号和s:
d[1][i+1][j+1+cnt]+=d[0][i][j](cnt=s中左括号数-右括号数)
- 尾巴加上右括号和s:
d[1][i+1][j-1+cnt]+=d[0][i][j](cnt=s中左括号数-右括号数)
- 从已经加上s的转移:
d[1][i+1][j+1]+=d[1][i][j]
d[1][i+1][j-1]+=d[1][i][j]
这些转移前提是要合法。合法情况还有一点要注意的是,s不一定都能随便放到p和q任何一个地方的,因为可能出现p+s的序列不合法,即p+s序列中存在前缀左括号数小于右括号数,所以还要用j这一维的值与cnt的值比较。
看了下题解,它的做法是求出dp[i][j],这个dp[i][j]既是前缀方案数又是后缀方案数,因为后缀相当于前缀反过来,其右括号数目大于等于左括号数目。通过枚举p的i和j来确定q,而q是后缀,而二者的方案数乘积为答案的一部分贡献。
另外这一题写完后直接提交差点点1A了,不过感觉还不错,难得考虑全面。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[][][];
int main(){
char ch;
int n,m,cnt=,precnt=;
scanf("%d%d",&n,&m);
int N=n-m;
for(int i=; i<m; ++i){
scanf(" %c",&ch);
if(ch=='(') ++cnt;
else --cnt;
precnt=min(precnt,cnt);
}
d[][][]=;
if(<=cnt&& cnt<=*N && precnt==) d[][][cnt]=;
for(int i=; i<N; ++i){
for(int j=; j<=*N; ++j){
if(j+<=*N){
d[][i+][j+]+=d[][i][j];
d[][i+][j+]%=;
}
if(j->=){
d[][i+][j-]+=d[][i][j];
d[][i+][j-]%=;
}
if(j+<=*N){
d[][i+][j+]+=d[][i][j];
d[][i+][j+]%=;
}
if(j->=){
d[][i+][j-]+=d[][i][j];
d[][i+][j-]%=;
}
if(<=j++cnt && j++cnt<=*N && j++precnt>=){
d[][i+][j++cnt]+=d[][i][j];
d[][i+][j++cnt]%=;
}
if(<=j-+cnt && j-+cnt<=*N && j-+precnt>=){
d[][i+][j-+cnt]+=d[][i][j];
d[][i+][j-+cnt]%=;
}
}
}
printf("%d",d[][N][]);
return ;
}
Codeforces 629C Famil Door and Brackets(DP)的更多相关文章
-
codeforces629C Famil Door and Brackets (dp)
题意:给你一个长度为n的括号匹配串(不一定恰好匹配),让你在这个串的前面加p串和后面加上q串,使得这个括号串平衡(平衡的含义是对于任意位置的括号前缀和大于等于0,且最后的前缀和为0). 思路:枚举这个 ...
-
codeforces 629C Famil Door and Brackets (dp + 枚举)
题目链接: codeforces 629C Famil Door and Brackets 题目描述: 给出完整的括号序列长度n,现在给出一个序列s长度为m.枚举串p,q,使得p+s+q是合法的括号串 ...
-
Codeforces 629C Famil Door and Brackets DP
题意:给你一个由括号组成的字符串,长度为m,现在希望获得一个长度为n(全由括号组成)的字符串,0<=n-m<=2000 这个长度为n的字符串要求有两个性质:1:就是任意前缀,左括号数量大于 ...
-
CodeForces 629C Famil Door and Brackets
DP. 具体做法:dp[i][j]表示长度为 i 的括号串,前缀和(左括号表示1,右括号表示-1)为 j 的有几种. 状态转移很容易得到:dp[i][j]=dp[i - 1][j + 1]+dp[i ...
-
codeforces 425C Sereja and Two Sequences(DP)
题意读了好久才读懂....不知道怎么翻译好~~请自便~~~ http://codeforces.com/problemset/problem/425/C 看懂之后纠结好久...不会做...仍然是看题解 ...
-
Codeforces Beta Round #13 C. Sequence (DP)
题目大意 给一个数列,长度不超过 5000,每次可以将其中的一个数加 1 或者减 1,问,最少需要多少次操作,才能使得这个数列单调不降 数列中每个数为 -109-109 中的一个数 做法分析 先这样考 ...
-
codeforces #267 C George and Job(DP)
职务地址:http://codeforces.com/contest/467/problem/C 太弱了..这题当时都没做出来..思路是有的,可是自己出的几组数组总是过不去..今天又又一次写了一遍.才 ...
-
Codeforces 403D: Beautiful Pairs of Numbers(DP)
题意:转换模型之后,就是1~n个数中选k个,放到一个容量为n的背包中,这个背包还特别神奇,相同的物品摆放的位置不同时,算不同的放法(想象背包空间就是一个长度为n的数组,然后容量为1的物体放一个格子,容 ...
-
CodeForces B. The least round way(dp)
题目链接:http://codeforces.com/problemset/problem/2/B B. The least round way time limit per test 5 secon ...
随机推荐
-
「C++」理解智能指针
*上面对于「智能指针」是这样描述的: 智能指针(英语:Smart pointer)是一种抽象的数据类型.在程序设计中,它通常是经由类型模板(class template)来实做,借由模板(tem ...
-
Linux Hadoop2.7.3 安装(单机模式) 二
Linux Hadoop2.7.3 安装(单机模式) 一 Linux Hadoop2.7.3 安装(单机模式) 二 YARN是Hadoop 2.0中的资源管理系统,它的基本设计思想是将MRv1中的Jo ...
-
(十五)ioctl、ifreq、ifconf
ioctl操作 传统上ioctl函数是用于那些普遍使用,但不适合归入其他类别的任何特性的系统接 口.Posix去掉了ioctl,它通过 创建特殊的其功能已被Posix标准化的包裹函数来代替ioct ...
-
持续集成工具Jenkins学习总结
概述 持续集成(Continuous Integration,简称CI)是一种软件开发实践,团队开发人员每次都通过自动化的构建(编译.发布.自动化测试)来验证,从而尽早的发现集成错误.持续集成最大的优 ...
-
各种数据分析图demo
极地蛛网图:http://www.hcharts.cn/demo/index.php?p=61 各种数据分析图demo: http://www.hcharts.cn/demo/index.php?p= ...
-
sublime text 2 运行 python时返回EOFError: EOF when reading a line错误
其主要原因是sublime text 2中python没有与 stdin(标准输入)连接所致,解决方法也很简单,那就是安装sublimeREPL插件,然后 Tools->sublimerepl- ...
-
setInterval定时和ajax请求
fnSetMarkPoint = function (param) { $.ajax({ success: function (returnValue) { window.setInterval(&q ...
-
解决: 移动端经mouseover显示出的弹层中链接点击问题
通常我们会遇到这样的需求,导航菜单在鼠标划过的时候显示自定义弹层,在弹层中有一些链接需要点击后跳转或者其他一些事件.比如: $(".menu li").on("mouse ...
-
JavaScript(一)
JavaScript介绍 JavaScript是运行在浏览器端的脚步语言,JavaScript主要解决的是前端与用户交互的问题,包括使用交互与数据交互. JavaScript是浏览器解释执行的,前端脚 ...
-
winform SerialPort串口通信问题
一.串口通信简介串行接口(串口)是一种可以将接受来自CPU的并行数据字符转换为连续的串行数据流发送出去,同时可将接受的串行数据流转换为并行的数据字符供给CPU的器件.一般完成这种功能的电路,我们称为串 ...