POJ 2955 Brackets (区间dp)

http://poj.org/problem?id=2955

字符串只包含两种括号,求其中最长的regular brackets.(可以不连续)

定义dp[i][j]为从i到j区间内的最多匹配数,并且第i个和第k个匹配,那么dp[i][j]=max(dp[i][j],dp[i+1][k]+dp[k+1][j]+2);

初始化的时候注意dp[i][j]一定是从dp[i+1][j]过来的.

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 int dp[105][105];
 6 char s[105];
 7 int main()
 8 {
 9     //freopen("a.txt","r",stdin);
10     while(~scanf("%s",s)&&strcmp(s,"end")!=0)
11     {
12         int l=strlen(s);
13         memset(dp,0,sizeof(dp)); //初始化
14         for(int i=l-1;i>=0;i--) //枚举左端点
15         {
16             for(int j=i+1;j<l;j++) //右端点
17             {
18                 dp[i][j]=dp[i+1][j]; //dp[i][j]一定是由dp[i+1][j]得来
19                 for(int k=i+1;k<=j;k++) //分段  如果第i个和第k个匹配
20                 {
21                     if(s[i]=='('&&s[k]==')'||s[i]=='['&&s[k]==']')
22                     dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);
23                 }
24             }
25         }
26         printf("%d
",dp[0][l-1]);
27     }
28     return 0;
29 }