题目描述 Description
我们用以下规则定义一个合法的括号序列：
（1）空序列是合法的
（2）假如S是一个合法的序列，则 (S) 和[S]都是合法的
（3）假如A 和 B 都是合法的，那么AB和BA也是合法的
例如以下是合法的括号序列：
(), [], (()), ([]), ()[], ()[()]
以下是不合法括号序列的：
(, [, ], )(, ([]), ([()
现在给定一些由'(', ')', '[', ，']'构成的序列 ，请添加尽量少的括号，得到一个合法的括号序列。
输入描述 Input Description
输入包括号序列S。含最多100个字符（四种字符： '(', ')', '[' and ']') ，都放在一行，中间没有其他多余字符。
最后一次把不合法的S变为合法的之前可能情况：
1）S形如（S′）或[S′]：
只需把S′变合法即可。
f[i,j]= f[i+1,j-1]
2）S形如（S′ 或[S′：
先把S′变为合法的，右边加 ）或]即可。
f[i,j]= f[i+1,j]+1
3）S形如 S′）或S′]：
先把S′化为合法的，左边加（或 [即可。
f[i,j]= f[i,j-1]+1
4）把长度大于1的序列SiSi+1…..Sj-1Sj分为两部分:
Si...... Sk，Sk+1….. Sj
分别化为规则序列.
则：f[i,j]=f[i,k]+f[k+1,j] ；i<=k<=j-1;
上述4种情况取最小值即可。
代码如下：
1 //codevs3657 括号序列 区间DP 2 //copyright by ametake 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn=100+10; 9 const int maxint=0x3f3f3f3f; 10 char s[100+10]; 11 int f[maxn][maxn]; 12 13 int main() 14 { 15 scanf("%s",s); 16 int n=strlen(s); 17 for (int i=0;i<n;i++) f[i][i]=1; 18 for (int p=1;p<n;p++) 19 { 20 for (int i=0;i<n-p;i++) 21 { 22 int j=i+p; 23 f[i][j]=maxint; 24 if ((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) 25 f[i][j]=min(f[i][j],f[i+1][j-1]); 26 if ((s[i]=='('&&s[j]!=')')||(s[i]=='['&&s[j]!=']')) 27 f[i][j]=min(f[i][j],f[i+1][j]+1); 28 if ((s[i]!='('&&s[j]==')')||(s[i]!='['&&s[j]==']')) 29 f[i][j]=min(f[i][j],f[i][j-1]+1); 30 for (int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); 31 } 32 } 33 printf("%d\n",f[0][n-1]); 34 return 0; 35 }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。