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

1141 Brackets Sequence

c 
阅读更多
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");
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics