【区间DP】Brackets

传送门:Brackets

题意:()与[ ]括号匹配,求有效匹配个数。

解法:简单区间DP

代码:

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

typedef long long LL;
using namespace std;
string str;
int dp[120][120];

inline LL max(LL a, LL b)
{
  return a >= b ? a : b;
}

inline bool pd(char a, char b)
{
  if ((a == '['&&b == ']') || (a == '('&&b == ')'))
    return true;
  else return false;
}
int  main()
{
  while (cin >> str && str!="end" )
  {
    memset(dp,0,sizeof(dp));
    for (int str_length = 2; str_length <= str.length(); str_length++)
    {
      for (int i = 0; i + str_length - 1 < str.length(); i++)
      {
        int j = i + str_length- 1 ;
        if (pd(str.at(i), str.at(j)))
        {
          dp[i][j] = 2 + dp[i + 1][j - 1];
        }
        for (int k = i; k <= j; k++)
          dp[i][j] = max(dp[i][k] + dp[k + 1][j], dp[i][j]);
      }
    }
    cout << dp[0][str.length()-1] << endl;
  }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 4 =