ZOJ 1463 Brackets Sequence

几乎和Folding是一样的题目,区别是这更简单一点。LRJ黑书里拿做动态规划例题的第一道。

  1#include <cstdio>
  2#include <string>
  3
  4#define min(x,y) ( x < y ? x : y )
  5
  6int T, m[101][101], L, ch[101][101];
  7char str[101];
  8
  9void dp ();
 10int get ( intint );
 11void init ();
 12void print ( intint );
 13
 14int main ()
 15{
 16    //freopen ( "bracket.in", "r", stdin );
 17    scanf ( "%d"&T );
 18    gets ( str );
 19    int i;
 20    for ( i = 0; i < T; i ++ )
 21    {
 22        if ( i ) 
 23            printf ( "\n" );
 24        init ();
 25        dp ();
 26        //printf ( "%d\n", ch[0][L - 1] );
 27        print ( 0, L - 1 );
 28        printf ( "\n" );
 29        //pt ();
 30    }

 31    return 0;
 32}

 33
 34void init ()
 35{
 36    gets ( str );
 37    gets ( str );
 38    L = strlen ( str );
 39    memset ( m, 0sizeof ( m ) );
 40    memset ( ch, 0xffsizeof ( ch ) );
 41}

 42
 43void dp ()
 44{    
 45    int i, j, p, k, t;
 46    for ( i = 0; i < L; i ++ )
 47        m[i][i] = 1;
 48    for ( p = 1; p <= L; p ++ )
 49    {
 50        for ( i = 0; i + p < L; i ++ )
 51        {
 52            int ans = 101;
 53            j = i + p;
 54            if ( str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']' )
 55            {
 56                t = m[i + 1][j - 1];
 57                if ( ans > t )
 58                    ch[i][j] = -2, ans = t;
 59            }

 60            if ( str[i] == '(' || str[i] == '[' )
 61            {
 62                t = m[i + 1][j] + 1;
 63                if ( ans > t )
 64                    ch[i][j] = i, ans = t;
 65            }

 66            if ( str[j] == ')' || str[j] == ']' )
 67            {
 68                t = m[i][j - 1+ 1;
 69                if ( ans > t )
 70                    ch[i][j] = j, ans = t;
 71            }

 72            for ( k = i; k < j; k ++ )
 73            {
 74                t = m[i][k] + m[k + 1][j];
 75                if ( ans > t )
 76                    ch[i][j] = k, ans = t;
 77            }

 78            m[i][j] = ans;
 79        }

 80    }

 81}

 82
 83void print ( int i, int j )
 84{
 85    if ( i > j )
 86        return;
 87    if ( i == j )
 88    {
 89        if ( str[i] == '(' || str[i] == ')' )
 90            printf ( "()" );
 91        else 
 92            printf ( "[]" );
 93        return;
 94    }

 95    else if ( ch[i][j] == -2 )
 96    {
 97        printf ( "%c", str[i] );
 98        print ( i + 1, j - 1 );
 99        printf ( "%c", str[j] );
100    }

101    else if ( ch[i][j] == j )
102    {
103        print ( i, j - 1 );
104        print ( j, j );
105    }

106    else
107    {
108        print ( i, ch[i][j] );
109        print ( ch[i][j] + 1, j );
110    }

111}

112
113

posted on 2008-02-27 13:02 杜仲当归 阅读(573) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。

导航

<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜