sdut 1451 括号东东 DP-白红宇

sdut 1451 括号东东 DP

阅读量：7130 次

发布时间：2019-06-28

本文共 1712 字，大约阅读时间需要 5 分钟。

题意：中文.....

思路：

pku有一道题，经典的括号匹配（区间DP）题目，那道题目是求的最长满足条件的子串的长度，那里的子串与这里的子串条件不一样。

详细：

对于这个例子

)((())))(()())

pku的最长子串是12

而这里是6

这里我们是求的连续的满足的子串。

dp[i]表示0到i的最长的满足的连续的子串

则有：

if(str[i - dp[i - 1] - 1] == '(' && str[i] == ')') dp[i] = dp[i - dp[i - 1] - 1] + 2;

if (dp[i - dp[i - 1] - 2])

dp[i] += dp[i - dp[i - 1] - 2]

//#pragma comment(linker,"/STACK:327680000,327680000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #define CL(arr, val) memset(arr, val, sizeof(arr))#define ll long long#define inf 0x7f7f7f7f#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll long long#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define N 1000007using namespace std;int dp[N];int ans,num;char str[N];int n;int main(){ // Read(); int i; while (~scanf("%s",str)) { n = strlen(str); CL(dp,0); num = 0; ans = 0; for (i = 1; i < n; ++i) { if (i - dp[i - 1] - 1 >= 0 && str[i - dp[i - 1] - 1] == '(' && str[i] == ')') { dp[i] = dp[i - 1] + 2; if (i - dp[i - 1] - 2 >= 0 && dp[i - dp[i - 1] -2] != 0) { dp[i] += dp[i - dp[i - 1] - 2]; } } if (ans < dp[i]) { ans = dp[i]; num = 1; } else if (ans == dp[i]) num++; } if (ans == 0) printf("0 1\n"); else printf("%d %d\n",ans,num); } return 0;}