[51nod1791] 合法括号子段 DP

题解：

　　首先我们需要发现一个性质，在括号序列不变的情况下，括号匹配是不会变的，因此不论子串怎么取，括号匹配的关系是不会变化的。这是一个很容易发现的性质，然而我太弱，没发现。

　　于是可以据此进行DP，我们记录下每个右括号与哪个左括号进行匹配，记为pos[i], 设f[i]表示DP到i位,子串以i结尾的方案数。

　　则对于一个i，如果它有pos[i],那么从pos[i] ~ i是一个合法的序列，那么这个的方案给答案贡献1。同时这段合法序列还可以和以pos[i] - 1结尾的合法子串进行两两搭配，所以转移方程为
　　$f[i] = f[pos[i] - 1] + 1;$

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define R register int
 4 #define AC 1101000
 5 #define LL long long
 6 
 7 int n;LL ans;
 8 int s[AC], top;
 9 int pos[AC], f[AC];
10 char ss[AC];
11 
12 inline void read()
13 {
14     int c = getchar();
15     while(c != ')' && c != '(') c = getchar();
16     while(c == ')' || c == '(') ss[++n] = c, c = getchar();
17 }
18 
19 void pre()
20 {
21     n = ans = top = 0;
22     read();
23     for(R i = 1; i <= n; i ++)
24     {
25         f[i] = pos[i] = 0;
26         if(ss[s[top]] == '(' && ss[i] == ')') pos[i] = s[top --];
27         else s[++top] = i;
28     }
29 }
30 
31 void write(LL x)
32 {
33     if(!x) {puts("0"); return ;}    
34     top = 0;
35     while(x) ss[++top] = x % 10 + '0', x /= 10;
36     for(R i = top; i; i --) putchar(ss[i]);
37     puts("");
38 }
39 
40 void get()
41 {
42     for(R i = 1; i <= n; i ++)
43     {
44         if(!pos[i]) continue;
45         f[i] += f[pos[i] - 1] + 1;
46         ans += f[i];
47     }
48     write(ans);
49     //printf("%lld
", ans);
50 }
51 
52 void work()
53 {
54     int T;
55     scanf("%d", &T);
56     while(T --) pre(), get();
57 }
58 
59 int main()
60 {
61 //    freopen("in.in", "r", stdin);
62     work();
63 //    fclose(stdin);
64     return 0;
65 }

View Code