Parentheses Sequence微软编程笔试
2024-09-05 23:15:51
描述
You are given a sequence S of parentheses. You are asked to insert into S as few parentheses as possible so that the resulting sequence T is well matched.
It's not difficult. But can you tell how many different T you can get?
Assume S = ()), you can get either (()) or ()().
输入
One line contains the sequence S.
For 30% of the data, 1 ≤ |S| ≤ 10
For 60% of the data, 1 ≤ |S| ≤ 200
For 100% of the data, 1 ≤ |S| ≤ 1000
输出
Output 2 integers indicating the minimum number of parentheses need to be inserted into S and the number of different T. The number of different T may be very large, so output the answer modulo 109+7.
())
1 2
只考虑左边(比右边)多的情况,也就是消掉匹配的()之后的比如(((((()消掉匹配的后只有(((((的情况
现在考虑如下"("比")"多
((()()( => ((( 那么第一个(和第二个(之间最多只能有1个),至少0个
那么第二个(和第三个(之间最多只能有2个),至少0个
那么第三个(和第四个(之间最多只能有3个),至少1个
那么第四个(和第五个(之间最多只能有3个),至少1个
dp[i][j]:到第i+1个"("为止,有j个")"的方案数
k表示当前第i个"("和第i+1个"("之间有k个")"
dp[i][j] = sum(dp[i-1][j-k])
那么))))())))())))*(((((()(((()((,*号左边全是消不掉的),右边全是消不掉(,右边也就是上面讨论的情况,左边翻转一下也就是上面讨论情况,ans = ansl*ansr%MOD;
最新文章
- django rest framework 再撸体验
- 工作中简单又实用的vim配置
- Flume环境部署和配置详解及案例大全
- Kali+Win7双系统
- POJ 3648 Wedding (2-SAT,经典)
- U当家U盘启动盘制作教程
- android文字阴影效果设置
- Mac系统升级到10.9(mavericks)时安装php扩展问题解决(转)
- spoj 10606 Balanced Numbers 数位dp
- 最全的Swift社交应用文本输入优化汇总
- POJ2407(欧拉函数)
- java_db常见错误总结
- gdb的多线程调试
- TOTP算法 基于时间的一次性密码
- 洛谷P2756 飞行员配对方案问题
- Oracle Database 快捷版 安装 连接
- Vue 给axios做个靠谱的封装(报错,鉴权,跳转,拦截,提示)
- JavaScript面试技巧之数组的一些不low操作
- nginx的启动,停止和重启
- 《JavaScript面向对象编程指南》读书笔记①