| 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 ( int, int, int );
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, 0, sizeof ( 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