首页 > 代码库 > 洛谷 P1241 括号序列
洛谷 P1241 括号序列
P1241 括号序列
题目描述
定义如下规则序列(字符串)：
1．空序列是规则序列；
2．如果S是规则序列，那么(S)和[S]也是规则序列；
3．如果A和B都是规则序列，那么AB也是规则序列。
例如，下面的字符串都是规则序列：
()，[]，(())，([])，()[]，()[()]
而以下几个则不是：
(，[，]，)(，())，([()
现在，给你一些由‘(’，‘)’，‘[’，‘]’构成的序列，你要做的，是找出一个最短规则序列，使得给你的那个序列是你给出的规则序列的子列。(对于序列a1，a2，…，an和序列bl，b2，…，bm，如果存在一组下标1≤i1<i2<…<in≤m，使得aj＝b(i,j)对一切1≤j≤n成立，那么a1，a2…，an就叫做b1，b2，…，bm的子列。
输入输出格式
输入格式：
输入文件仅一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，长度不超过100。
输出格式：
输出文件也仅有一行，全部由‘(’，‘)’，‘]’，‘]’组成，没有其他字符，把你找到的规则序列输出即可。因为规则序列可能不止一个，因此要求输出的规则序列中嵌套的层数尽可能地少。
输入输出样例
输入样例#1：
([()
输出样例#1：
()[]()
说明
输出解释：
{最多的嵌套层数为1，如层数为2时的一种为()[()]}
jsoi2011
/*69分 维护栈*/#include<cstdio>#include<iostream>#include<cstring>using namespace std;const int MAXN=120;const int INF=0x7fffffff;int f[MAXN][MAXN],a[MAXN][MAXN];char s[MAXN];int n;void aaaa(int x,int y){ if (x>y) return; if (x==y) { if (s[x]==‘(‘||s[x]==‘)‘) printf("()"); else printf("[]"); } else { if (a[x][y]==-1) { if(s[x]==‘(‘) { printf("("); aaaa(x+1,y-1); printf(")"); } else { printf("["); aaaa(x+1,y-1); printf("]"); } } else { aaaa(x,a[x][y]); aaaa(a[x][y]+1,y); } } } int main(){ // gets(s); scanf("%s",&s); n=strlen(s); memset(f,0,sizeof(f)); for (int i=n;i>0;i--) { s[i]=s[i-1]; f[i][i]=1; } int tot; for (int p=1;p<=n;p++) { for (int i=1;i<=n-p;i++) { int j=i+p; f[i][j]=INF; if ((s[i]==‘(‘&&s[j]==‘)‘)||(s[i]==‘[‘&&s[j]==‘]‘)) { tot=f[i+1][j-1]; if (f[i][j]>tot) f[i][j]=tot; } a[i][j]=-1; for (int k=i;k<j;k++) { tot=f[i][k]+f[k+1][j]; if (f[i][j]>tot) { f[i][j]=tot; a[i][j]=k; } } } } aaaa(1,n); return 0;}
洛谷 P1241 括号序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。