ZOJ 2711 Regular Words

2770323 2008-03-04 21:15:46 Accepted 2711 C++ 00:00.21 20388K C.D.=.=


考虑当前有a个A,b个B,c个C时的情况为f(a,b,c),得到f(a,b,c)= f(a-1,b,c)+f(a,b-1,c)+f(a,b,c-1)。注意边界以及限定情况。值得注意的是此题用int数组时会越界。

  1#include <cstdio>
  2#include <string>
  3
  4int N;
  5char f[61][61][61][90];
  6
  7void dp ();
  8void print ( intintint );
  9
 10int main ()
 11{
 12    //freopen ( "in.txt", "r", stdin );
 13    dp ();
 14    while ( scanf ( "%d"&N ) == 1 )
 15    {
 16        //printf ( "%0.0f\n", f[N][N][N] );
 17        print ( N, N, N );
 18        printf ( "\n" );
 19    }

 20    return 0;
 21}

 22
 23void print ( int a, int b, int c )
 24{
 25    int i;
 26    for ( i = 89; i >= 0; i -- )
 27    {
 28        if ( f[a][b][c][i] )
 29            break;
 30    }

 31    if ( i == -1 )
 32        printf ( "0\n" );
 33    else
 34    {
 35        for ( ; i >= 0; i -- )
 36            printf ( "%d", f[a][b][c][i] );
 37        printf ( "\n" );
 38    }

 39}

 40
 41void dp ()
 42{
 43    int a, b, c, l, i, ac = 0;
 44    memset ( f, 0sizeof ( f ) );
 45    f[1][0][0][0= 1;
 46    for ( l = 2; l <= 180; l ++ )
 47    {
 48        for ( a = 0; a <= l && a <= 60; a ++ )
 49        {
 50            for ( b = 0; b <= a && b <= 60; b ++ )
 51            {
 52                c = l - a - b;
 53                if ( c > b )
 54                    continue;
 55                if ( c < 0 )
 56                    break;
 57                if ( a > 0 )
 58                {
 59                    //f[a][b][c] += f[a - 1][b][c];        
 60                    ac = 0;
 61                    for ( i = 0; i < 90; i ++ )
 62                    {
 63                        f[a][b][c][i] += f[a - 1][b][c][i] + ac;
 64                        if ( f[a][b][c][i] >= 10 )
 65                            ac = 1, f[a][b][c][i] -= 10;
 66                        else 
 67                            ac = 0;
 68                    }
                    
 69                }

 70                if ( b > 0 )
 71                {
 72                    //f[a][b][c] += f[a][b - 1][c];    
 73                    ac = 0;
 74                    for ( i = 0; i < 90; i ++ )
 75                    {
 76                        f[a][b][c][i] += f[a][b - 1][c][i] + ac;
 77                        if ( f[a][b][c][i] >= 10 )
 78                            ac = 1, f[a][b][c][i] -= 10;
 79                        else 
 80                            ac = 0;
 81                    }

 82                }

 83                if ( c > 0 )
 84                {
 85                    //f[a][b][c] += f[a][b][c - 1];
 86                    ac = 0;
 87                    for ( i = 0; i < 90; i ++ )
 88                    {
 89                        f[a][b][c][i] += f[a][b][c - 1][i] + ac;
 90                        if ( f[a][b][c][i] >= 10 )
 91                            ac = 1, f[a][b][c][i] -= 10;
 92                        else
 93                            ac = 0;
 94                    }

 95                }

 96            }

 97        }

 98    }

 99}

100
101

posted on 2008-03-04 21:28 杜仲当归 阅读(279) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

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

导航

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

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜