cf314E. Sereja and Squares(dp)

题意

题目链接

给你一个擦去了部分左括号和全部右括号的括号序列,括号有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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1012
来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

2529
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

1846
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

1927
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

702
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

922
来自专栏数据结构与算法

1083 Cantor表

题目描述 Description 现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的: 1/1 1/2 ...

3117
来自专栏程序员叨叨叨

5.2 数组类型

在着色程序中,数组通常的使用目的是:作为从外部应用程序传入大量参数到 Cg 的顶点程序中的形参接口,例如与皮肤形变相关的矩阵数组,或者光照参数数组等。

591
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

44410
来自专栏HTML5学堂

算法之旅 | 选择排序法

HTML5学堂-码匠:数据快速的计算与排序,与前端页面性能有直接的关系。由于排序的算法有很多,在本次“算法系列”的分享当中,我们先从简单易上手的选择排序法开始,...

3275

扫码关注云+社区