必威体育Betway必威体育官网
当前位置:首页 > IT技术

Brackets

时间:2019-08-30 16:11:06来源:IT技术作者:seo实验室小编阅读:77次「手机版」
 

brackets

这里写图片描述

这里写图片描述

1.dp[i][j]表示从i到j匹配的括号的最大数量。

2.转移方程dp[i][j] = max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);

表示当第k个括号和第i个括号匹配时,即ss[i] == ss[k]

括号数量为第i+1~k-1的括号数量和第k+1~j的括号数量+2

#include<iOStream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
string ss;
int dp[105][105];

int main()
{
    char ss[105];
    while(~scanf("%s",ss+1))
    {
        if(strcmp(ss+1,"end") == 0)
        break;
        int len = strlen(ss+1);
        memset(dp,0,sizeof(dp));

        for(int i = len-1 ; i>=1 ; i--)
        {
            for(int j = i+1 ; j<=len ;j++)
            {
                dp[i][j] = dp[i+1][j];
                if(ss[i] == '('||ss[i]=='[')
                {
                    for(int k = i+1 ; k <= j ; k++)
                    {
                        if(ss[i]=='('&&ss[k]==')'||ss[i]=='['&&ss[k]==']')
                        dp[i][j] = max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);
                    }   
                }

            }
        }


        cout<<dp[1][len]<<endl;
    }

    return 0;
}

相关阅读

用栈解决----括号匹配问题(MatchBrackets)

问题:给出一个字符数组,判断里边的括号是否匹配。 分析:首先我们要确定用什么方法来解决这个问题,然后再进一步分析过程。 我们可以用

分享到:

栏目导航

推荐阅读

热门阅读