首页 > 代码库 > dp1141
dp1141
定义如下规则序列（字符串）：
空序列是规则序列；
如果S是规则序列，那么（S）和[S]也是规则序列；
如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()， []， (())， ([])， ()[]， ()[()]
这几个则不是规则序列：
(， [， ]， )(， ([()
现在，给出一些由‘(’，‘)’，‘[’，‘]’构成的序列，请添加尽量少的括号，得到一个规则序列。
如果a[i]a[j]括号配对 d[i][j]=min(d[i+1][j-1],d[i][k]+d[k][j]) k=i...j ，不管匹配与否都需要重新遍历可能的分割。最优解必定是遍历各个可能结果后得到的，因此需要遍历。但不光要遍历，还要考虑到最优解不止通过分割得到，还有可能本身i,j匹配 如果不配对 d[i][j]=min(d[i][k]+d[k][j]) k=i...j 最少添加的括号数就是d[1][n]
本题和算法导论的矩阵链加括号类似，都是需要先考虑更小的结
构，再逐步扩大到更大的结构中。
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;#define maxn 300char st[maxn];int f[maxn][maxn], v[maxn][maxn];bool match(char a, char b){ if (a ==‘(‘&& b ==‘)‘) return true; if (a ==‘[‘&& b ==‘]‘) return true; return false;}void output(int s, int e){ if (s > e) return; if (s == e)//表示自己只能跟自己配对 { if (st[s] ==‘(‘|| st[s] ==‘)‘) printf("()"); else printf("[]"); return; } if (v[s][e] ==-1)//不需要分割,v值没有改变 { putchar(st[s]); output(s +1, e -1); putchar(st[e]); return; } output(s, v[s][e]); output(v[s][e] +1, e);}int main(){ //freopen("t.txt", "r", stdin); if (gets(st) == NULL) return 0; int len = strlen(st); int i,j,k; memset(f, -1, sizeof(f)); memset(v, -1, sizeof(v));//v初值都是-1 for (i =0; i < len; i++) { f[i][i] =1; f[i +1][i] =0; } for ( i =1; i < len; i++) { for ( j =0; j < len - i; j++) { int s = j, e = j + i; //i表示长度，最大是len-1， //S,J表示起点，最大为LEN-2，此时I为1，即长度只能为1 //这里遍历的时候，先考虑长度为2的单位，再考虑长度3， //依次类推 f[s][e]=999;//如果if不执行，后面的f[s][e]找不到 if (match(st[s], st[e])) f[s][e] = f[s +1][e -1]; //如果f(2,3)正好匹配，那么f(2,3)=f(3,2)=0，表示不需要添加//还需要考虑从中间分割的情况，两个极端情况是分成s，s和s+1，e；s,e-1和ee //v[s][e]如果改变了，则说明需要分割，不改变，说明S,E匹配。因此首先设V为-1，假定不改变 for ( k = s; k < e; k++) if (f[s][e] > f[s][k] + f[k +1][e]) { f[s][e] = f[s][k] + f[k +1][e]; v[s][e] = k; } } } output(0, len -1); putchar(‘\n‘); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。