【UOJ 456】括号匹配

淡淡的烟草味﹌ 2021-10-26 21:44 291阅读 0赞

【题目描述】：  
  
我们给出了“正则括号”序列的归纳定义：  
  
空序列是一个正则括号序列，  
  
如果S是一个正则括号序列，则（s）和\[s\]是正则括号序列，  
  
如果A和B是正则括号序列，则AB是正则括号序列。  
  
没有其他序列是正则括号序列。  
  
例如，下列都是正则括号序列：  
  
(), \[\], (()), ()\[\], ()\[()\] 而下列都不是：  
  
(, \], )(, (\[)\], (\[(\] 给出一个的只有'(',')','\[','\]'四种括号组成的序列S，你的目标是找到最长的正则括号序列的长度，该序列是S的子序列。子序列即删除部分字符后余下的序列。  
  
例如：给定初始序列(\[(\[\]\])\]，最长正则括号子序列是\[(\[\])\]。  
【输入描述】：  
  
包含多个测试用例。每个输入测试用例都只有'(',')','\[','\]'的单行组成；每个输入测试的长度在1到100之间，文件的结尾用包含“end”的一行标出，不应该被处理。  
【输出描述】：  
  
对于每个输入，程序应该在单行上打印最长可能的正则括号子序列的长度。  
【样例输入】：  
  
((()))  
()()()  
(\[\]\])  
)\[)(  
(\[\]\[\]\[)  
end  
  
【样例输出】：  
  
6  
6  
4  
0  
6  
  
【时间限制、数据范围及描述】：  
  
时间：1s 空间：64M  
  
对于 30%的数据：字符串长度小于等于10；  
  
对于100%的数据：字符串长度小于等于100；数据组数<=10；  
  
题解：区间dp啦啦啦、（poj 2955）  
   1.匹配：dp\[i\]\[j\]=dp\[i+1\]\[j-1\]+2;  
   2.不匹配：枚举k为断点，然后p\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i\]     \[k\]+dp\[k+1\]\[j\]);  
   3.读入的方式注意一下就行了！是int n=strlen(s+1);不是int n=strlen(s);唉，找好长时间！

#include<bits/stdc++.h>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cmath>
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    using namespace std;
    char s[105];
    int dp[107][107],n;
    int main(){
        freopen("456.in","r",stdin);
        freopen("456.out","w",stdout);
        while(1){
            scanf("%s",s+1);
            if(s[1]=='e' && s[2]=='n') break;
            memset(dp,0,sizeof(dp));
            int n=strlen(s+1);
            //cout<<n;
            for(int l=2;l<=n;l++){
                for(int i=1; i<=n && i+l-1<=n ;i++){
                    int j=i+l-1;
                    if(s[i]=='(' && s[j]==')') dp[i][j]=dp[i+1][j-1]+2;
                    if(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+1][j]);
                }
            }
            printf("%d\n",dp[1][n]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11139645.html