I saw this problem last summer vacation …
I haven't understood the solution Feel difficult to understand …
I wanted to give up this time …
Finally, I hardened my head and figured it out …
Thank you for being stubborn and naive hhh
subject ：
Several questions that need to be clear ：
① On the validity of bracket sequence ： For a sequence of parentheses , From left to right , One character at a time , For each parenthesis sequence --‘(’-- quantity Greater than or equal to --‘)’--
quantity , Then the whole sequence of parentheses is legal .
② about --‘(’-- and --’)’--
The addition of can be discussed separately ： Parentheses are added to the space between parentheses in the original sequence , If the left bracket and the right bracket add different spaces , Then they must not affect each other . If the same gap is added , Then the addition of the right bracket must precede the left bracket , Otherwise, parentheses are paired , Add meaningless , There is no effect of order , So it doesn't affect each other , So we will discuss its addition separately .
③ After the second point above is clear , How to use it to solve problems ： After we can discuss it separately , We can judge whether adding left parentheses to the original parenthesis sequence makes it legal , Then transform the original bracket sequence （ Reverse the sequence of parentheses first , Then change the left bracket into the right bracket , The right bracket becomes the left bracket ）, After this adjustment, we add the left bracket to the transformed bracket sequence to make it legal （ This is equivalent to adding a closing parenthesis to the original parenthesis sequence ）.
The following is an example ：
Usually we only need to add one kind of bracket to make the whole bracket sequence legal .
for example
Original bracket sequence ：（（（） The number of left parentheses is greater than or equal to the number of right parentheses , legitimate , No need to add
Transformed sequence ：（））） The number of left parentheses is less than the number of right parentheses , wrongful , Need to add
But there are special circumstances , Both brackets are required
Original bracket sequence ：) ) ( ( At first glance, it seems equal , After understanding the first point, we know that this sequence is illegal , Need to add .
Transformed sequence ：) ) ( ( The parentheses are the same as the original sequence , wrongful , Need to add .
In this way, our problem becomes the problem of adding left parentheses to the bracket sequence to make it legal , So every time you encounter a right parenthesis , We can add an open parenthesis before it , From just legal （ The left and right brackets are equal ） To more left parentheses （ The upper limit is the length of the bracket sequence ）.
④dp Meaning of array ： The explanations of the questions are the same as before , But in that way, I feel that there are always some problems I can't understand .
I thought of a meaning （ In fact, it is similar to the original meaning , But it's better understood ）:
dp[i][j] Refers to the front i Before parenthesis characters I don't know how many to add ( Can be 0 individual ) --’(’-- Make this before i Bracket characters are legal （ What is the meaning of legality --’(’-- than
--’)’-- Many or equal , therefore j from 0 start ) Number of species .
It may be a little awkward … Take out the parentheses and note it ： front i I don't know how many left parentheses are added before the parenthesis characters i The number of legal parenthesis characters .
In other words, we don't care how many we add , We only consider how many left parentheses are more than right parentheses in the added results . and j Yes, the subscript must be greater than or equal to 0, So if dp[i][j] This state can exist, so this value must not be 0, That is, it can't be 0 species .
⑤ Recurrence formula ：
encounter --‘(’-- : We only consider --‘)’-- Add before --‘(’--
Make the sequence of parentheses before the right parenthesis legal . When encountering the left parenthesis , Prove that the sequence of parentheses before the left parenthesis has been judged how to make it legal , So it's still legal to add this left parenthesis , So we don't need to worry about the left parenthesis . That is, add left parentheses to the bracket sequence in front of him to make its legal number equal to the number of left parentheses to be added to the sequence after adding this left parenthesis .
dp[i][j]=dp[i-1][j-1];
encounter --‘)’-- ： If the sequence with the closing parenthesis itself is legal , Then we just need to add 0 An open parenthesis makes it legal , If it is not legal, you need to add an open bracket that just makes it legal, or even more .
dp[i][j] = dp[i-1][0] + dp[i-1][1] + … + dp[i-1][j] + dp[i-1][j+1]
explain ：
To get the front i There are more left parentheses than right parentheses in a sequence of characters j Legal status of a
Can be
front i-1 There are more left parentheses than right parentheses in a sequence of characters 0 individual （ Just legal ） Situation , Before the closing bracket j+1 Left parentheses get
front i-1 There are more left parentheses than right parentheses in a sequence of characters 1 A case in point , Before the closing bracket j Left parentheses get
.
.
.
front i-1 There are more left parentheses than right parentheses in a sequence of characters j+1 A case in point , Before the closing bracket 0 Left parentheses get
（ In fact, the distribution between the left and right parentheses is the number of these parentheses ）
But doing that above will definitely time out
Then notice
dp[i][j-1] = dp[i-1][0] + dp[i-1][1] + … dp[i-1][j]
∴dp[i][j] = dp[i-1][j+1] + dp[i][j-1]
Similar to multiple knapsacks, it uses the state of the current line
initialization ：dp[0][0]=1 This is obvious
Other details are in the notes ：
#include <iostream> #include <cstring> #include <algorithm> #include <stdio.h>
using namespace std; typedef long long LL; const int MOD=1000000007; const int N
=5010; LL dp[N][N]; char str[N]; int len; LL func() { memset(dp,0,sizeof(dp));
dp[0][0]=1; for(int i=1;i<=len;i++)// A bracket a bracket judgment { if(str[i]=='(') { for(int j=1
;j<=len;j++) { dp[i][j]=dp[i-1][j-1];// Don't think about it dp[i][0] because dp[i-1][-1] It's illegal non-existent by 0
} } else { dp[i][0]=(dp[i-1][0]+dp[i-1][1])%MOD;// Special judgment to prevent cross-border The data here is short , The inference before optimization is used for(int
j=1;j<=len;j++) { dp[i][j]=(dp[i-1][j+1] + dp[i][j-1])%MOD; } } } for(int i=0;i
<=len;i++) if(dp[len][i]) return dp[len][i];
// What we need is a length of len Legality of adding parentheses , The first possible case of traversal from front to back is the case where the number of parentheses is the least , Because there can be many left parentheses , We only need to add the least cases
return -1; } int main() { scanf("%s",str+1);// Subscript from 1 start len=strlen(str+1); LL l=
func(); reverse(str+1,str+len+1); for(int i=1;i<=len;i++) { if(str[i]=='(') str[
i]=')'; else str[i]='('; } LL r=func(); cout<<l*r%MOD; return 0; }
Technology