codevs 3657 括号序列

时间限制: 1 s

空间限制: 256000 KB

题目描述 Description

我们用以下规则定义一个合法的括号序列：

（1）空序列是合法的

（2）假如S是一个合法的序列，则 (S) 和[S]都是合法的

（3）假如A 和 B 都是合法的，那么AB和BA也是合法的

例如以下是合法的括号序列：

(), [], (()), ([]), ()[], ()[()]

以下是不合法括号序列的：

(, [, ], )(, ([]), ([()

现在给定一些由'(', ')', '[', ，']'构成的序列，请添加尽量少的括号，得到一个合法的括号序列。

输入描述 Input Description

输入包括号序列S。含最多100个字符（四种字符： '(', ')', '[' and ']') ，都放在一行，中间没有其他多余字符。

输出描述 Output Description

使括号序列S成为合法序列需要添加最少的括号数量。

样例输入 Sample Input

([()

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【样例说明】
最少添加2个括号可以得到合法的序列：()[()]或([()])
【数据范围】
S的长度<=100 (最多100个字符)。

规则序列的子序列：

1、若S 形如 (S') 、 [S'] 把S'变为规则的即可

2、若 S 形如 (S' 那么把S' 变成规则的，再+1

若 S 形如 S') 、 [S' 、 S'] 与上面情况类似

3、只要序列长度大于1，就可以视为两个序列拼接后的结果，所以可以把S分为两部分 Si...Sk Sk+1...Sj

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[101];
int ans=201,f[101][101];
/*int dfs(int l,int r)  记忆化搜索法 
{
    if(l>r) return 0;
    if(l==r) return 1;
    if(f[l][r]<201) return f[l][r];
    if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')) f[l][r]=min(f[l][r],dfs(l+1,r-1));
    if(s[l]=='('||s[l]=='[') f[l][r]=min(f[l][r],dfs(l+1,r)+1);
    if(s[r]==']'||s[r]==')') f[l][r]=min(f[l][r],dfs(l,r-1)+1);
    for(int i=l;i<r;i++) f[l][r]=min(f[l][r],dfs(l,i)+dfs(i+1,r));
    return f[l][r];
}*/
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
     for(int j=0;j<len;j++)
       {
              if(i==j) f[i][j]=1;
              else if(i>j) f[i][j]=0;
              else f[i][j]=201;
       }
    /*int p=dfs(0,len-1);
    printf("%d",p);*/
    for(int k=2;k<=len;k++) //DP法 
     for(int l=0;l+k-1<len;l++)
      {
            int r=l+k-1;
            if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))  f[l][r]=min(f[l][r],f[l+1][r-1]);
            if(s[l]=='('||s[l]=='[')   f[l][r]=min(f[l][r],f[l+1][r]+1);
            if(s[r]==']'||s[r]==')')   f[l][r]=min(f[l][r],f[l][r-1]+1);
            for(int i=l;i<r;i++)   f[l][r]=min(f[l][r],f[l][i]+f[i+1][r]);
      }
    printf("%d",f[0][len-1]);
}

同时我们又可以发现，情况2的所有状态，在情况3里都有表示，所以可以去掉

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[101];
int ans=201,f[101][101];
int main()
{
    scanf("%s",s);
    int len=strlen(s);
    for(int i=0;i<len;i++)
     for(int j=0;j<len;j++)
       {
              if(i==j) f[i][j]=1;
              else if(i>j) f[i][j]=0;
              else f[i][j]=201;
       }
    for(int k=2;k<=len;k++) 
     for(int l=0;l+k-1<len;l++)
      {
            int r=l+k-1;
            if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')) 
            f[l][r]=min(f[l][r],f[l+1][r-1]);
          for(int i=l;i<r;i++) f[l][r]=min(f[l][r],f[l][i]+f[i+1][r]);
      }
    printf("%d",f[0][len-1]);
}