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 条评论
登录 后参与评论

相关文章

来自专栏程序员叨叨叨

5.2 数组类型

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

651
来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

5284
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

3475
来自专栏JavaEdge

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

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

1152
来自专栏技术之路

算法时间复杂度

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

1876
来自专栏编程

Python内置函数int高级用法

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

2619
来自专栏dalaoyang

递归基础思想

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

P1168 中位数

题目描述 给出一个长度为N的非负整数序列A[i],对于所有 ]的中位数。 个数的中位数。 输入输出格式 输入格式: 输入文件median.in的第1...

32211
来自专栏互联网大杂烩

快速排序

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

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

1083 Cantor表

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

3137

扫码关注云+社区

领取腾讯云代金券