本文共 3922 字,大约阅读时间需要 13 分钟。
1、
2、题目大意
给出一个字符串,只包含()[]四种符号,添加最少的符号使得该字符串有序,跟前面做的括号的问题类似,上次是求字符串中有规律的子串的最长长度,这次是求最少添加多少字符使得有序,并且输出最终有序的字符串来
dp[i][j]表示i到j区间内字符有序添加的最小值,
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]
else
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
3、AC代码:
#include #include #include using namespace std;#define N 105char s[N];int dp[N][N];int v[N][N];int check(char a,char b){ if(a=='(' && b==')') return 1; if(a=='[' && b==']') return 1; return 0;}void output(int l,int r){ if(l>r) return ; if(l==r) { if(s[l]=='(' || s[l]==')') printf("()"); else printf("[]"); return ; } if(v[l][r]==-1) { printf("%c",s[l]); output(l+1,r-1); printf("%c",s[r]); return ; } output(l,v[l][r]); output(v[l][r]+1,r);}int main(){ //while(scanf("%s",s)!=EOF) //{ //while多次输入wrong answer scanf("%s",s); int len=strlen(s); memset(dp,-1,sizeof(dp)); memset(v,-1,sizeof(v)); for(int i=0; i dp[j][k]+dp[k+1][e] || dp[j][e]==-1) { v[j][e]=k; dp[j][e]=dp[j][k]+dp[k+1][e]; } } } } output(0,len-1); printf("\n"); //} return 0;}
4、题目:
Time Limit: 1000MS | | Memory Limit: 65536K |
Total Submissions: 23444 | | Accepted: 6595 | | Special Judge |
Description
Let us define a regular brackets sequence in the following way:
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
Input
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Sample Output
()[()]
Source
Time Limit: 1000MS | | Memory Limit: 65536K |
Total Submissions: 23444 | | Accepted: 6595 | | Special Judge |
Description
Let us define a regular brackets sequence in the following way:
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
Input
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Sample Output
()[()]
Source
转载地址:http://bgddi.baihongyu.com/