专栏首页ACM小冰成长之路51Nod-1612-合法表达式

51Nod-1612-合法表达式

ACM模版

描述

题解

我们需要考虑到能够加多少括号以及加括号的动态规划过程,这里格外要注意一个问题,就是初始字符串不合法,并且无论怎么加都不合法的情况,比如 5//4,这是真实存在的一组样例,是第三组样例,结果应该输出 0。

代码

#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 3e5 + 10;
const int MOD = 1e6 + 3;

int n, m;
int f[MAXN];
char s[MAXN];

int main()
{
    scanf("%s", s);
    n = (int)strlen(s);
    m = 2 * n;
    f[m] = 1;
    for (int i = 0; i < n; i++)
    {
        if (s[i] < '0')
        {
            if (s[i] == '+' || s[i] == '-' || (i && s[i - 1] >= '0'))
            {
                m--;
            }
            else    //  考虑到不合法的串,比如 5//4
            {
                puts("0");
                return 0;
            }
        }
        else if (s[i + 1] < '0')
        {
            for (int j = m + n; j > m; j--)
            {
                f[j - 1] = (f[j - 1] + f[j]) % MOD;
            }
        }
    }

    printf("%d\n", f[m]);

    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 51Nod-1149-Pi的递推式

    ACM模版 描述 ? 题解 image.png 代码 #include <cstdio> #include <algorithm> #include <cmat...

    f_zyj
  • 51Nod-1203-JZPLCM

    ACM模版 描述 ? 题解 这个题的解法好像好多好多,可以线段树解,自然也可以用树状数组解,还有大佬直接莫队推过,我这里用的树状数组搞得。 首先将数进行拆解,拆...

    f_zyj
  • POJ-3866-Exclusive Access 2

    ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

    f_zyj
  • PAT (Basic Level) Practice (中文)1013 数素数

    令 P​i表示第 i 个素数。现任给两个正整数 M≤N≤104,请输出 PM到 PN的所有素数。

    C you again 的博客
  • 蓝桥杯 基础练习 杨辉三角形

    输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出,中间使用一个空格分隔。请不要在前面输出多余的空格。

    Debug客栈
  • BZOJ 1061: [Noi2008]志愿者招募【单纯形裸题】

    1061: [Noi2008]志愿者招募 Time Limit: 20 Sec  Memory Limit: 162 MB Submit: 4813  Solv...

    Angel_Kitty
  • PAT (Basic Level) Practice (中文)1007 素数对猜想

    让我们定义d​n为:dn=pn+1−pn,其中p​i是第i个素数。显然有d1=1,且对于n>1有d​n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数...

    C you again 的博客
  • HDU4576 Robot(概率)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack
  • P1018 乘积最大

    题目描述 今年是国际数学联盟确定的“2000――世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智...

    attack
  • CSU1216: 异或最大值(01Trie树)

    多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

    attack

扫码关注云+社区

领取腾讯云代金券