POJ2955 Brackets

一、题目内容

【题目描述】

题目大意：给你一串()[]括号，要你求出这串括号的最大匹配个数，如’(‘与’)’匹配，为2个，’[‘与’]’匹配，为2个，其他不能匹配…….

【输入格式】

输入有多组样例，每组样例为一行字符，end时结束。

【输出格式】

每个样例输出一个答案，占一行

【输入样例】

((()))
()()()
([]])
)[)(
([][][)
end

【输出样例】

6
6
4
0
6

【测试网站】

poj2955

二、题目分析

dp[i][j]代表从区间i到区间j所匹配的括号的最大个数，首先，假设不匹配，那么dp[i][j]=dp[i+1][j]；然后查找i+1~~j有木有与第i个括号匹配的

假设存在：
dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k][j]+2)…..

注意有多组数据，dp数组不能开得太大，开2000*2000 TLE了

三、代码示例

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;
const int maxn = 1000 + 10;

int dp[maxn][maxn];

int main()
{
  char str[maxn];
  while(~scanf("%s",str) && str[0] != 'e')
  {
  int n = strlen(str);
//  dp[i][j] = max(dp[i+1][j-1] + 1, dp[i+1][j], dp[i][j-1]);
  memset(dp,0,sizeof(dp));
  for(int i = n-1; i >= 0; i--)
    for(int j = i+1; j < n; j++)
      {
        if((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']'))
        dp[i][j] = max(dp[i][j],dp[i+1][j-1]+1);
        for(int k = i+1; k < j; k++)
        dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]);
      }
  printf("%d\n",2*dp[0][n-1]);
}
return 0;
}