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 ( 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
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 ( int, int );
11void init ();
12void print ( int, int );
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, 0, sizeof ( m ) );
40 memset ( ch, 0xff, sizeof ( 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
2008年2月26日
摘要: 2761550
2008-02-26 14:10:05
Accepted
1505
C++
00:00.11
3480K
C.D.=.=
...
阅读全文
2008年2月25日
摘要: 2760648
2008-02-25 15:11:56
Accepted
1554
C++
00:00.56
980K
C.D.=.=
...
阅读全文
2008年2月11日
2008年2月8日
摘要: 2746723
2008-02-08 20:54:30
Accepted
2281
C++
00:01.51
25832K
C.D.
...
阅读全文
2008年2月7日
摘要: 2745991
2008-02-07 15:05:00
Accepted
2278
C++
00:00.68
1708K
C.D.
...
阅读全文
2008年2月5日
2008年2月4日
求N排列中逆序数对为K对的个数。
需要一个小技巧。一个形为{2，1，5，3，4}的5-排列，可以转化为一个{0，1，0，1，1}的排列。这里每个元素A
i表示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}