FZU2030(括号匹配)

时间：2022-03-02 03:28:31

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110977#problem/E

题目大意：略

题目思路：数据范围很小，可以搜索，但是如果数据范围较大则只能DP

用二维数组表示状态dp[i][j]表示扫描到第i个字符时有j个'（'还未完成匹配，而答案就是dp[len-1][0] len表示字符串长度，

dp[len-1][0]表示扫描完最后一个字符后没有未匹配的'（'.

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

using namespace std;

#define gamma 0.5772156649015328606065120 //欧拉常数

#define MOD 100000007

#define inf 0x3f3f3f3f

#define N 100005

#define maxn 10001000

typedef long long LL;

typedef pair<int,int> PII;

char str[];

int dp[][];

int main()

{

    int i,m,j;

    int x,y,v;

    while(scanf("%s",str)!=EOF)

    {

        mst(dp,);

        dp[][]=;

        int len=strlen(str);

        for(i=; i<len; ++i)

            for(j=; j<len; ++j)

            {

                if(str[i]=='(')   ///扫到一个'（'则应该和j-1个'('情况相同

                {

                    if(j)

                        dp[i][j]=dp[i-][j-];

                }

                else if(str[i]==')')   ///扫到一个')'则该和j+1个'('相同，因为当前的')'会消去一个'('

                {

                    dp[i][j]=dp[i-][j+];

                }

                else   ///如果是?则可以加'(',也可以加')'所以两种情况都要加

                {

                    dp[i][j]=dp[i-][j+];

                    if(j) dp[i][j]+=dp[i-][j-];

                }

            }

        printf("%d\n",dp[len-][]);

    }

    return ;

}

相关文章