题目链接:

http://hihocoder.com/problemset/problem/1300

题解:

先用栈预处理出每个‘)’匹配的‘(’的位子,放在pos数组中。

dp[i]表示以i结尾的合法子串个数,则易知转移方程:

dp[i]=dp[pos[i]-1]+1;

代码:

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std; typedef long long LL;
const int maxn = 1e6 + ; char str[maxn];
LL dp[maxn];
int pos[maxn]; void init() {
memset(pos, , sizeof(pos));
memset(dp, , sizeof(dp));
} int main() {
while (scanf("%s", str + ) == ) {
int len = strlen(str + );
init();
stack<int> ms;
for (int i = ; i <= len; i++) {
if (str[i] == '(') {
ms.push(i);
}
else {
if (!ms.empty()) {
int j = ms.top(); ms.pop();
pos[i] = j;
}
}
}
LL ans = ;
for (int i = ; i <= len; i++) {
if(pos[i]>=) dp[i] = dp[pos[i] - ] + ;
ans += dp[i];
}
printf("%lld\n", ans);
}
return ;
}

最新文章

  1. SharePoint 2013 图文开发系列之InfoPath入门
  2. 足球运动训练心得及经验分析-c语言学习调查
  3. Delphi下的OpenGL开发入门
  4. [Sciter系列] MFC下的Sciter&ndash;3.Sciter脚本与底层交互
  5. 在Mac上通过Sublime、Skim编辑LaTeX
  6. ASP.NET会员注册登录模块(MD5加密,Parameters防止SQL注入,判断是否注册)
  7. SSM框架+Plupload实现断点续传(Spring+SpringMVC+MyBatis+Plupload)
  8. CI 笔记4 (easyui 手风琴)
  9. asp.net word内容读取到页面
  10. mac上的kindle打开mobi文件的方式
  11. 关于Android 7.0(API24)相机的问题汇总
  12. dom操作相关,byebye T T
  13. .Net Core应用框架Util介绍(四)
  14. HBase JavaAPI
  15. Linux学习笔记之十二————vim编辑器的分屏操作
  16. OPENWRT路由3G拔号实验
  17. PAT甲级 1124. Raffle for Weibo Followers (20)
  18. Effective MySQL之SQL语句最优化——读书笔记之二
  19. wordpress 点击文章图片 不能编辑(chrome下面) wordpress Uncaught DOMException: Failed to execute &#39;setBaseAndExtent&#39; on &#39;Selection&#39;: There is no child at offset 1.
  20. java的线程安全、单例模式、JVM内存结构等知识学习和整理

热门文章

  1. IOS添加控件
  2. 如何使用10个小时搭建出个人域名而又Geek的独立博客?
  3. Mac下配置cocos2dx2.2.6的Android环境
  4. 实例:使用纹理对象创建Sprite对象
  5. php_1
  6. 11个优秀的HTML5 &amp; CSS3下拉菜单制作教程
  7. HashSet和LinkedHashSet特点.
  8. java 设计模式之单例模式
  9. 什么是WEB服务器?
  10. LVS-HA