[POJ2955]Brackets

约定不等于承诺〃 2023-08-17 17:38 145阅读 0赞

#### 题面描述 ####

我们给出了正则括号序列的如下归纳定义：  
· 空序列是正则括号序列  
· 如果s是正则方括号序列，那么(s)和\[s\]是正则方括号序列  
· 如果a和b是正则括号序列，那么ab是正则括号序列  
· 没有其它序列是正则括号序列  
例如，以下所有字符序列都是正则方括号序列：  
()  
\[\]  
(())  
()\[\]  
()\[()\]  
而以下字符序列都不是：  
(  
j  
)  
给定字符的方括号序列s，找到s的正则括号子序列的最大长度。

#### 输入格式 ####

输入若干行字符串，以end为结尾

#### 输出格式 ####

每行输出该字符串的最大正则子序列长度，end不输出

#### 样例 ####

##### 样例输入 #####

((()))  
()()()  
(\[\]\])  
)\[)(  
(\[\]\[\]\[)  
end

##### 样例输出 #####

6  
6  
4  
0  
6

#### 题解 ####

很容易想到\\(O(n)\\)的假算法，即从左往右查询合法括号的总数量即可。但事实上，这种算法碰到这种情况会WA掉：\\\[(\[)\]\\\]  
因此，我们还是选择使用区间DP。每次查询到一组括号的两端分别在i和j时，使当前答案dp\[i\]\[j\]=dp\[i+1\]\[j-1\]+2，即该区间内的最大正则括号序列+2。我们再遍历i到j内的所有组合，取最大值即可。

#include<iostream>
    #include<cstdio>
    #define int long long
    #define maxn 1000
    //#define local
    using namespace std;
    int n;
    string s;
    int dp[maxn][maxn];
    inline void work(){
        for(register int i=0;i<maxn;i++){
            for(register int j=0;j<maxn;j++)dp[i][j]=0;
        }
        n=s.size();
        int ans=0;
        for(register int i=n-1;i>=0;i--){
            for(register int j=i+1;j<n;j++){
                if(s[i]=='(' && s[j]==')' || s[i]=='[' && s[j]==']')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][j]);
            }
        }
        cout<<dp[0][n-1]<<endl;
    }
    signed main(){
        #ifdef local
        freopen("1.txt","r",stdin);
        #endif
        ios::sync_with_stdio(false);
        cin.tie(0); 
        cin>>s;
        while(s!="end"){
            work();
            cin>>s;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Chen574118090/p/11608602.html