【算法?日更?第八期】区间动态规划：1572：括号配对题解

 1 #include 2 #include 3 #include 4 using namespace std;
 5 string s;int n,wrong;
 6 stackint>a;
 7 int main()
 8 {
 9     cin>>s;
10     n=s.length();
11     for(int i=0;i)
12     {
13         if(s[i]==‘(‘) a.push(1);
14         else if(s[i]==‘)‘) 
15         {
16             if(!a.empty())
17             {
18                 if(a.top()==1) a.pop();
19                 else wrong++;
20             }
21             else wrong++;
22         }
23         else if(s[i]==‘[‘) a.push(2);
24         else if(s[i]==‘]‘) 
25         {
26             if(!a.empty())
27             {
28                 if(a.top()==2) a.pop();
29                 else wrong++;
30             }
31             else wrong++;
32         }
33     }
34     coutwrong;
35     return 0;
36 }

 1 #include 2 #include 3 using namespace std;
 4 string s;int n,f[1000][1000];
 5 int main()
 6 {
 7     cin>>s;
 8     n=s.length();
 9     for(int t=1;t1;t++)
10     for(int i=0;i)
11     {
12         int j=i+t;
13         if((s[i]==‘(‘&&s[j]==‘)‘)||(s[i]==‘[‘&&s[j]==‘]‘)) f[i][j]=f[i+1][j-1]+2;
14         for(int k=i;k)
15         f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
16     }
17     cout0][n-1];
18     return 0;
19 }