`
SaraWon
  • 浏览: 43320 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

1141 Brackets Sequence

阅读更多
POJ上的1141题目是Brackets Sequence
输入一个由(、)、[、]四个字符组成的字符串

规定如下的字符串是合格的:
1.空串是合格的;
2.如果S是合格的,那么(S)和[S]也是合格的
3.如果A和B是合格的,那么AB也是合格

对于一个不合格的字符串,总能通过添加一些字符使之成为合格的。
题目要求:输入一个字符串,输出最短合格字符串

Sample Input:
([)]
Sample Output:
()[()]

这个题目还是DP问题,我对于DP问题不是特别熟悉,所以做起来还是有些吃力。而且本题要记录路径

解题思路:
dd[i][j]表示从i到j的字符串转换为合格字符串所需要添加的最少字符数。
显然,如果字符串长度为1,则dd[i][i]=1;
如果字符串形如(S)或者(s'),则dd[i][j]=dd[i+1][j-1]
否则,dd[i][j]=min{dd[i][k]+dd[k+1][j]}
path[i][j]表示从i到j最佳划分的位置,即k值
显然,path[i][i]=i,同时如果形如(S)或[S],规定path[i][j]=-1

注意:1.还是要采用自底向上的方法,否则会超时
     2.对于形如(S)或者[S]的字符串,S中间有可能存在')(',此时左右的括号匹配不是最合适,仍然需要划分求解,比较哪种情况下的值最小

#include<stdio.h>
char seq[110]; //输入字符串
int dd[110][110],path[110][110];
//查找路径,当发现seq[i]需要添加字符时
//如果seq[i]是括号时,将其设置为'0'
//seq[i]是中括号时,将其设置为'1'
void printPath(int start,int end,int path[][110]){
    int k;
    if(start>end)
        return;
    k=path[start][end];
    //可能存在[][]的情况,所以要循环
    while(k==-1||k==-2){
        if(end-start>1)
        {
            if(k==-1)
            {    start=start+1;end=end-1;   }
            else
                start=start+2;
            k=path[start][end];                
        }
        else
            return;
    }
    //递归到了单个字符,设置0和1
    if(start==end&&start==k)
    {
        if(seq[start]=='('||seq[start]==')')
            seq[start]='0';
        else
            seq[start]='1';
    }
    if(start!=end){
        printPath(start,k,path);
        printPath(k+1,end,path);
    }
}
int main()
{
    int len;
    int i,j,k;
    int temp;
    
    memset(dd,0,sizeof(dd));
    gets(seq);
    len=strlen(seq);
    //初始化
    for(i=0;i<len;i++)
    {    dd[i][i]=1;path[i][i]=i;   }
    //i代表步长,即从j开始,长度为i的字符串
    //j代表字符串开始位置
    //k代表分割位置,范围是(j,j+i)
    for(i=1;i<len;i++)
    {
        for(j=0;j+i<len;j++)
        {
            dd[j][j+i]=999;
            //如果形式为()或[]
            if((seq[j]=='('&&seq[j+i]==')')||
                (seq[j]=='['&&seq[j+i]==']')){
                if((seq[j]=='('&&seq[j+1]==')')||
                    (seq[j]=='['&&seq[j+1]==']')){
                    dd[j][j+i]=dd[j+2][j+i];
                    path[j][j+i]=-2;
                }
                else{ 
                    dd[j][j+i]=dd[j+1][j+i-1];
                    path[j][j+i]=-1;
                }
            }
            //分割
            for(k=j;k<=j+i;k++)
            {
                temp=dd[j][k]+dd[k+1][j+i];
                if(dd[j][j+i]>temp)
                {    dd[j][j+i]=temp;path[j][j+i]=k;    }
            }
                        
        }
        
    }
    //printf("%d\n",dd[0][len-1]);
    printPath(0,len-1,path);
    //print path
    for(i=0;i<len;i++)
    {
        if(seq[i]=='0')
            printf("()");
        else if(seq[i]=='1')
            printf("[]");
        else
            printf("%c",seq[i]);
    }
    printf("\n");
}

分享到:
评论

相关推荐

    pku 1141 Brackets Sequence

    这里是两种AC1141的两种代码,解题报告我空间有 http://hi.csdn.net/dongdong331

    poj题目分类...

    * 1141 Brackets Sequence * 1159 Palindrome * 1160 Post Office * 1163 The Triangle * 1458 Common Subsequence * 1579 Function Run Fun * 1887 Testing the CATCHER * 1953 World Cup Noise * 2386 Lake ...

    pku题目分类

    - **题目编号**:1125 Stockbroker Grapevine, 1141 Brackets Sequence, 1160 Post Office, 1163 The Triangle - **描述**:这些题目通常涉及到图的遍历、最短路径等问题。 - **示例**: - **1125 Stockbroker ...

    算法分类以及POJ题目分类

    4. 1141 Brackets Sequence:与括号匹配相关,可以使用动态规划来确定合法括号序列。 5. 1160 Post Office:经典的最短路径问题,可以使用动态规划或Floyd-Warshall算法。 6. 1458 Common Subsequence:寻找两个字符...

    POJ各题算法分类和题目推荐 ACM必看

    * 1141 Brackets Sequence:本题目使用动态规划来计算括号序列的最长长度。 * 1159 Palindrome:本题目使用动态规划来计算回文串的最长长度。 * 1160 Post Office:本题目使用动态规划来计算邮局的最短距离。 * 1458...

    北京大学acm题库 题目分类

    相关题目有:1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579...

    Fractions to Decimals

    If the decimal representation has a repeating sequence of digits, indicate the sequence by enclosing it in brackets. For example, 1/3 = .33333333...is denoted as 0.(3), and 41/333 = 0.123123123...is ...

    poj题目类型总结(每题用到的算法)

    - **1141 (Brackets Sequence)**:本题要求判断括号序列是否有效,可以用栈来实现高效的判断。 ### 6. 数学 - **1458 (Common Subsequence)**:这是一个典型的数学问题,涉及组合数学中的组合数计算。 - **1017, ...

    算法艺术与信息学竞赛题目完全解析

    - **题目示例**:Pku1141——Brackets Sequence,通过动态规划解决子问题重叠的现象。 - **状态空间搜索**: - **题目示例**:Pku1480——Optimal Programs,适用于解决搜索空间较大但可通过剪枝优化的问题。 ##...

    datastage帮助文档

    A right arrow between menu commands indicates you should choose each command in sequence. For example, “Choose File &gt; Exit” means you should choose File from the menu bar, then choose Exit from the...

    代码 动态规划 特殊数据结构搜索、枚举

    1049 Brackets 特殊数据结构 1004 Prince Ray’s Puzzle 树状数组 1010 选队长 二叉树 1022 Longest Common Sequence 也可用二叉搜索树(nlog时间)解决,见llj的书 1025 最近公共祖先(LCA) 也可转化为RMQ问题,见...

    算法艺术与信息学竞赛题目完全解析.pdf

    - PKU 1141 — Brackets Sequence 问题,通过动态规划求解括号序列的有效性。 - PKU 1191 — 棋盘分割 问题,通过动态规划求解分割棋盘的最大价值。 #### 六、状态空间搜索 - **定义**:状态空间搜索是一种通过...

    SGU推荐题目分类

    181 X-Sequence 找循环节:X-Sequence 是 SGU 中的一道数学题目,要求找到循环节。 182 Open the Brackets 搜索:Open the Brackets 是 SGU 中的一道搜索题目,要求使用搜索算法来解决。 183 Painting the balls ...

    idea插件汇总-2,本系列资源一共有两份 全网独有

    9. Rainbow Brackets:彩虹括号插件,不同层级的括号以不同颜色显示,使嵌套代码更易读。 10. SequenceDiagram:用于生成序列图,帮助理解方法调用关系,可导出为图像。 11. RestfulToolkit:搜索Spring MVC项目中...

    Extended Backus Naur Form

    - `[]`: Square brackets denote an optional part of the syntax. - `{}`: Curly braces indicate that the enclosed part of the syntax can be repeated zero or more times. - `|`: The vertical bar represents...

    OJ练习题ABC

    DNA序列分析 (DNA Sequence Analysis) 这段代码的功能是寻找一个DNA序列中最富含“C”或“G”的子串。DNA序列由字符'A', 'T', 'C', 'G'组成,其中"C"和"G"代表较高含量的碱基。 - **核心算法**:滑动窗口技术,...

    计算机组成教学课件:Chapter2 Machine Instruction.ppt

    The process of instruction execution typically follows a straight-line sequence, unless interrupted by branching or looping mechanisms. 3. Register Transfer Notation (RTN) RTN is a notation used to ...

    算法解析ACM

    **案例分析:Pku1141—Brackets Sequence** 题目描述:给定一个括号序列,需要判断其是否合法。此类问题可以通过动态规划来解决,通过记录前缀序列的括号匹配状态来判断整个序列的合法性。 **案例分析:Pku1191—...

    编译原理龙书答案

    any string derived from the grammar can be considered to be a sequence consisting of 11, 1001 and 0, and not prefixed with 0. the sum of this string is: sum = Σn (21 + 20) * 2 n + Σm (23 + 20) * 2m ...

    Sql for mysql

    5.9 The Scalar Expression Between Brackets . . . . . . . . . . . . . . . . 106 viii Contents 5.10 The Scalar Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.11 Casting of ...

Global site tag (gtag.js) - Google Analytics