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
4
int N;
5
char f[61][61][61][90];
6
7
void dp ();
8
void print ( int, int, int );
9
10
int 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
23
void 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
41
void 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
6
int T, m[101][101], L, ch[101][101];
7
char str[101];
8
9
void dp ();
10
int get ( int, int );
11
void init ();
12
void print ( int, int );
13
14
int 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
34
void 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
43
void 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
83
void 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
4
const int MAXN = 20;
5
6
int m[21][201][MAXN], N, K;
7
8
void 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
24
void 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
43
void 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
61
int 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
}