138.括號序列（區間型DP）

3657 括號序列

?

時間限制: 1 s

空間限制: 256000 KB

題目等級 : 黃金 Gold

題解

查看運行結果

題目描述?Description

我們用以下規則定義一個合法的括號序列：

（1）空序列是合法的

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

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

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

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

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

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

?現在給定一些由'(', ')', '[', ，']'構成的序列，請添加盡量少的括號，得到一個合法的括號序列。

輸入描述?Input Description

輸入包括號序列S。含最多100個字符（四種字符： '(', ')', '[' and ']') ，都放在一行，中間沒有其他多余字符。

輸出描述?Output Description

使括號序列S成為合法序列需要添加最少的括號數量。

樣例輸入?Sample Input

? ?

([()

樣例輸出?Sample Output

? ?

2

數據范圍及提示?Data Size & Hint

? ?

【樣例說明】
最少添加2個括號可以得到合法的序列：()[()]或([()])
【數據范圍】
S的長度<=100?(最多100個字符)。

代碼：

#include< iostream >

using namespace std;

char p[101];

int f[101][101];

#include< cstdio >

#include< cstring >

int main()

{

scanf("%s",p+1);

int lena=strlen(p+1);

for(int i=1;i<=lena;++i)

f[i][i]=1;

for(int i=lena-1;i>=1;--i)

for(int j=i+1;j<=lena;++j)

{

f[i][j]=9999999;

for(int k=i;k<=j-1;++k)

{

if(((p[i]=='('&&p[j]==')')||(p[i]=='['&&p[j]==']'))&&i+1==j) f[i][j]=0;?

if(((p[i]=='('&&p[j]==')')||(p[i]=='['&&p[j]==']'))&&i+1!=j)

f[i][j]=min(min(f[i][j],f[i+1][j-1]),f[i][k]+f[k+1][j]);

else f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);

}

}

printf("%d\n",f[1][lena]);

return 0;

}