2008年3月4日

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 @ 2008-03-04 21:28 杜仲当归 阅读(267) | 评论 (0)编辑 收藏

2008年2月27日

几乎和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 @ 2008-02-27 13:02 杜仲当归 阅读(556) | 评论 (0)编辑 收藏

2008年2月26日

     摘要: 2761550 2008-02-26 14:10:05 Accepted 1505 C++ 00:00.11 3480K C.D.=.= ...  阅读全文
posted @ 2008-02-26 14:20 杜仲当归 阅读(398) | 评论 (1)编辑 收藏

2008年2月25日

     摘要: 2760648 2008-02-25 15:11:56 Accepted 1554 C++ 00:00.56 980K C.D.=.= ...  阅读全文
posted @ 2008-02-25 15:21 杜仲当归 阅读(181) | 评论 (0)编辑 收藏

2008年2月11日

菜题。即便是这样我还是写了三遍……步长开的太大,结果精度不高。

把A^B == B^A两边求对数,很容易得到ln(x)/x的函数。求导,此函数在e两侧单调。故可用二分。

 1/*
 2    二分逼近ln(x)/x = ln(a)/a
 3*/

 4
 5#include <cstdio>
 6#include <cmath>
 7
 8#define ZERO 1e-14
 9#define E exp(1.0f
10
11double A;
12
13int main ()
14{
15    //freopen ( "in.txt", "r", stdin );
16    while ( scanf ( "%lf"&A ) != EOF )
17    {
18        if ( A - E > ZERO )
19            printf ( "-1\n" );
20        else
21        {
22            double high, low, mid, d;
23            high = 45, low = E;
24            while ( high - low >= ZERO )
25            {
26                mid = ( high + low ) / 2;
27                d = log ( mid ) / mid - log ( A ) / A;
28                if ( d < ZERO && d > -ZERO )
29                    break;
30                else if ( d > ZERO )
31                {
32                    low = mid + 0.0000001;
33                }

34                else if ( d < -ZERO )
35                {
36                    high = mid - 0.0000001;
37                }

38            }

39            printf ( "%0.5f\n", mid );
40            d = fabs ( log ( mid ) / mid - log ( A ) / A );
41            //printf ( "error %0.8f\n", d );
42        }

43    }

44    return 0;
45}
posted @ 2008-02-11 14:18 杜仲当归 阅读(314) | 评论 (0)编辑 收藏

2008年2月8日

     摘要: 2746723 2008-02-08 20:54:30 Accepted 2281 C++ 00:01.51 25832K C.D. ...  阅读全文
posted @ 2008-02-08 21:29 杜仲当归 阅读(189) | 评论 (0)编辑 收藏

2008年2月7日

     摘要: 2745991 2008-02-07 15:05:00 Accepted 2278 C++ 00:00.68 1708K C.D. ...  阅读全文
posted @ 2008-02-07 15:30 杜仲当归 阅读(112) | 评论 (0)编辑 收藏

2008年2月5日

好吧,这其实是一道菜题。


 1#include <cstdio>
 2#include <string>
 3
 4const int MAXN = 1000000;
 5int b[2][3393000];
 6
 7int main ()
 8{
 9    memset ( b, 0, sizeof ( b ) );
10    int i, j;
11    for ( i = 2; i <= 1000000; i ++ )
12        b[0][i] = 1;
13    for ( i = 2; i <= 1000; i ++ )
14    {
15        j = MAXN / i;
16        while ( j > i )
17        {
18            b[0][i * j] += i + j;
19            j --;
20        }

21        b[0][i * i] += i;            
22    }

23    for ( i = 1; i <= 1000000; i ++ )
24    {
25        b[1][b[0][i]] ++;
26    }

27    int sum = 0;
28    for ( i = 0; i < 3393000; i ++ )
29    {
30        sum += b[1][i];
31        b[0][i] = sum;
32    }

33
34    //freopen ( "in.txt", "r", stdin );
35    int N;
36    while ( scanf ( "%d"&N ) != EOF )
37    {
38        if ( N > 3392928 )
39            printf ( "1000000\n" );
40        else
41            printf ( "%d\n", b[0][N] );
42    }

43    return 0;
44}
posted @ 2008-02-05 14:19 杜仲当归 阅读(244) | 评论 (0)编辑 收藏

2008年2月4日

求N排列中逆序数对为K对的个数。

需要一个小技巧。一个形为{2,1,5,3,4}的5-排列,可以转化为一个{0,1,0,1,1}的排列。这里每个元素Ai表示i前逆序数的对数。易证明两者一一对应。

这样就把问题转化为求åAi=K,Ai<=i的排列个数。设F(i,j)表示前i个数之和达到j的排列个数,DP打表即得解。

 1#include <cstdio>
 2#include <string>
 3
 4const int MAXN = 20;
 5
 6int m[21][201][MAXN], N, K;
 7
 8void add ( int x1, int m1, int x2, int m2 )
 9{
10    int i;
11    for ( i = 0; i < MAXN; i ++ )
12    {
13        m[x1][m1][i] += m[x2][m2][i];
14    }

15    int c = 0;
16    for ( i = 0; i < MAXN; i ++ )
17    {
18        int t = c + m[x1][m1][i];
19        c = t / 10;
20        m[x1][m1][i] = t % 10;
21    }

22}

23
24void print ( int x1, int m1 )
25{
26    //printf ( "$%d\n", m[x1][m1][1] );
27    int i;
28    for ( i = MAXN - 1; m[x1][m1][i] == 0 && i >= 0; i -- )
29        ;
30    if ( i == -1 )
31    {
32        printf ( "0" );
33    }

34    else
35    {
36        for ( ; i >= 0; i -- )
37        {
38            printf ( "%d", m[x1][m1][i] );
39        }

40    }

41}

42
43void dp ()
44{
45    memset ( m, 0, sizeof ( m ) );
46    int i, j, k;
47    m[0][0][0= 1;
48    for ( i = 1; i < 20; i ++ )
49    {
50        for ( j = 0; j < 200; j ++ )
51        {
52            for ( k = 0; k <= i && j - k >= 0; k ++ )
53            {
54                add ( i, j, i - 1, j - k );
55            }

56        }

57    }

58    //pt ();
59}

60
61int main ()
62{
63    //freopen ( "in.txt", "r", stdin );
64    dp ();
65    while ( scanf ( "%d %d"&N, &K ) )
66    {
67        if ( N == 0 && K == 0 )
68        {
69            break;
70        }

71        print ( N - 1, K );
72        printf ( "\n" );
73    }

74    return 0;
75}
posted @ 2008-02-04 15:01 杜仲当归 阅读(439) | 评论 (0)编辑 收藏
仅列出标题  

导航

<2017年7月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜