cf314E. Sereja and Squares(dp)
2018-09-29 03:52:50来源:博客园 阅读 ()
题意
题目链接
给你一个擦去了部分左括号和全部右括号的括号序列,括号有25种,用除x之外的小写字母a~z表示。求有多少种合法的括号序列。答案对4294967296取模。
合法序列不能相交,如()[],([])是合法序列,而([)]是不合法的。
Sol
这个题告诉我们什么叫:暴力艹标算,n方过百万。。。
首先当左括号确定之后,右括号的摆放顺序是确定的。
假设左括号只有一种
设$f[i][j]$表示前$i$个位置放了$j$个右括号
转移的时候分两种情况讨论
若该位置为$?$
放左括号的方案为$f[i - 1][j]$
放右括号的方案为$f[i - 1][j - 1]$
由于到第$i$个位置,最多有$i/2$个右括号。
当然还有一个下界$i - \frac{n}{2}$。
上界和下界都是为了保证序列合法
trick:对$2^{32}$取模相当于unsigned int 自然溢出
等等。。这题是个假题吧。。。。。
如果序列全都是????????
我算的最坏复杂度是$O(\frac{n^2}{8} + \frac{n^2}{16})$.......
#include<bits/stdc++.h> #define ui unsigned int using namespace std; const int MAXN = 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, cnt; ui f[MAXN]; char s[MAXN]; int main() { N = read(); if(N & 1) return puts("0"), 0; scanf("%s", s + 1); f[0] = 1; for(int i = 1; i <= N; i++) { if(s[i] == '?') for(int j = (i >> 1); j >= max(1, i - N / 2); j--) f[j] += f[j - 1]; else cnt++; } ui ans = 1; for(int i = 1; i <= N / 2 - cnt; i++) ans *= 25; cout << ans * f[N >> 1]; return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:sublime实现背景透明化
下一篇:CONTEST1001 题解
- C++ rand函数 2020-06-10
- Android P HIDL demo代码编写 (原创) 2020-05-07
- C++ STL框架 2020-03-29
- AtCoder Grand Contest 043--A - Range Flip Find Route 2020-03-22
- 在Android平台使用SNPE应链接libc++库 2020-03-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash