FZU2030(括号匹配)

题目链接：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[20];
int dp[20][20];

int main()
{
    int i,m,j;
    int x,y,v;
    while(scanf("%s",str)!=EOF)
    {
        mst(dp,0);
        dp[0][1]=1;
        int len=strlen(str);
        for(i=1; i<len; ++i)
            for(j=0; j<len; ++j)
            {
                if(str[i]=='(')   ///扫到一个'（'则应该和j-1个'('情况相同
                {
                    if(j)
                        dp[i][j]=dp[i-1][j-1];
                }
                else if(str[i]==')')   ///扫到一个')'则该和j+1个'('相同，因为当前的')'会消去一个'('
                {
                    dp[i][j]=dp[i-1][j+1];
                }
                else   ///如果是?则可以加'(',也可以加')'所以两种情况都要加
                {
                    dp[i][j]=dp[i-1][j+1];
                    if(j) dp[i][j]+=dp[i-1][j-1];
                }
            }
        printf("%d\n",dp[len-1][0]);
    }
    return 0;
}

FZU2030(括号匹配)

推荐阅读