首页 > 代码库 > POJ-2955 Brackets(括号匹配问题)

POJ-2955 Brackets(括号匹配问题)

2024-09-18 09:31:27   217人阅读

题目链接：http://poj.org/problem?id=2955

这题要求求出一段括号序列的最大括号匹配数量

规则如下：

  • the empty sequence is a regular brackets sequence,
  • if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
  • if a and b are regular brackets sequences, then ab is a regular brackets sequence.
  • no other sequence is a regular brackets sequence

分析题目的时候发现，这个和回文子序列统计有点类似，当i,j匹配时，它就可以从区间i+1,j-1的最大匹配数转移过来。除此之外，无论是否匹配，都可以从区间[i,k]+区间[k+1,j]求和而来（这里不用担心k会打断括号匹配导致数量减少，因为枚举k的过程中，一定会找到括号匹配的边界）。

所及构造dp[i][j]表示区间内的最大匹配数量，转移方式见代码。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cstring>
#define LL long long int
using namespace std;

const int mod=10007;
int dp[105][105];
string s;
bool ok(int i,int j)
{
    if(s[i]==‘[‘&&s[j]==‘]‘)
        return true;
    if(s[i]==‘(‘&&s[j]==‘)‘)
        return true;
    return false;
}

int main(){
    int n,k;
    cin.sync_with_stdio(false);
    while(cin>>s)
    {
        if(s=="end")
            break;
        for(int i=0;i<s.length();i++)
            fill(dp[i],dp[i]+105,0);
        for(int i=s.length()-1;i>=0;i--)
            for(int j=0;j<s.length();j++)
            {
                if(i>=j)
                    continue;
                if(ok(i,j))
                {
                    if(i+1==j)
                        dp[i][j]=2;
                    else
                    {
                        dp[i][j]=dp[i+1][j-1]+2;
                        for(int k=i;k<=j;k++)
                            dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
                    }
                }
                else
                {
                    if(i+1!=j)
                        for(int k=i;k<=j;k++)
                            dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
                }
            }
        cout<<dp[0][s.length()-1]<<endl;
    }

    return 0;
}

 

POJ-2955 Brackets(括号匹配问题)


联系
我们