[ACM]携程预赛第一场括号匹配（动态规划）

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 110   Accepted Submission(s) : 46

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Input

Output

Sample Input

4
[]
([])[]
((]
([)]

Sample Output

0
0
3
2

Source

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=250;
const int inf=0x7fffffff;
char str[maxn];
int dp[maxn][maxn],ps[maxn][maxn];
//dp[i][j]代表串从i到j需要添加几个字符才能合法，ps[i][j]，记录的从i到j在哪里断成两部分
int len;

int main()
{
    int k;cin>>k;
    while(k--)
    {
        cin>>str;
        len=strlen(str);
        memset(dp,0,sizeof(dp));
        for(int i=0;i(dp[i][mid]+dp[mid+1][j]))
                {
                    dp[i][j]=dp[i][mid]+dp[mid+1][j];
                    ps[i][j]=mid;//mid为串i到j区间断开的位置
                }
            }
        }
        cout<