poj 2955 Brackets

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

区间dp

题意：给你一串()[]括号，要你求出这串括号的最大匹配长度，如'('与')'匹配，为2个，'['与']'匹配，为2个，其他不能匹配。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 char str[1000];
 7 int dp[1000][1000];
 8 
 9 int main()
10 {
11     while(scanf("%s",str)!=EOF)
12     {
13         if(!strcmp(str,"end")) break;
14         int n=strlen(str);
15         memset(dp,0,sizeof(dp));
16         for(int i=n-2; i>=0; i--)
17         {
18             for(int j=i+1; j<n; j++)
19             {
20                 dp[i][j]=dp[i+1][j];
21                 for(int k=i+1; k<=j; k++)
22                 {
23                     if((str[i]=='('&&str[k]==')')||(str[i]=='['&&str[k]==']'))
24                     {
25                         dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k][j]+2);
26                     }
27                 }
28             }
29         }
30         printf("%d
",dp[0][n-1]);
31     }
32     return 0;
33 }

View Code