题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1502
题目大意：找出总的满足条件的字符串数,num(a)=num(b)=num(c)且任何前缀均满足num(a)>=num(b)>=num(c)
解题思路：用dp[i][j][k]表示a取i个,b取j个,c取k个的状态下最多有多少种满足条件的情况,容易推得状态转移方程如下：
dp[i][j][k]=dp[i-1][j][k](i>j时)+dp[i][j-1][k](j>k时)+dp[i][j][k-1](k>0时)
根据该状态转移方程即可输出最后的结果dp[n][n][n]
因为本题的数据结果比较大，所以还需要用到高精度，对不会用java的人就只能手敲一个大数相加了。。。
1
#include<cmath>
2
#include<cstdio>
3
#include<cstring>
4
#include<iostream>
5
#include<algorithm>
6
#define
scan(a) scanf("%d",&a)
7
using
namespace
std;
8
#define
N 61
9
char
dp[N][N][N][
100
],a[
100
];
10
void
init()
11
{
12
strcpy(dp[
0
][
0
][
0
],
"
1\0
"
);
13
strcpy(dp[
1
][
1
][
0
],
"
1\0
"
);
14
strcpy(dp[
1
][
0
][
1
],
"
0\0
"
);
15
strcpy(dp[
1
][
0
][
0
],
"
1\0
"
);
16
}
17
18
void
add(
char
*
p)
19
{
20
int
x,l,i,jin=
0
;
21
l=
strlen(a);
22
int
now=
0
;
23
for
(i=
0
;p[i]!=
'
\0
'
;i++
)
24
//
从加数开始一位一位访问
25
{
26
if
(i>=
l)
27
x=p[i]-
'
0
'
+jin;
//
i超过了a的长度
28
else
29
x=p[i]-
'
0
'
+a[i]-
'
0
'
+
jin;
30
if
(x>
9
)
31
{
32
jin=x/
10
;
33
x%=
10
;
34
}
35
else
36
jin=
0
;
37
a[now++]=x+
'
0
'
;
38
}
39
while
(jin)
40
{
41
if
(l<=
now)
42
{
43
a[now++]=(jin%
10
)+
'
0
'
;
44
jin/=
10
;
45
}
46
else
47
{
48
x=a[now]-
'
0
'
;
49
x+=
jin;
50
if
(x>
10
)
51
{
52
jin=x/
10
;
53
x%=
10
;
54
}
55
else
56
jin/=
10
;
57
a[now++]=x+
'
0
'
;
58
}
59
}
60
if
(now>
l)
61
a[now]=
'
\0
'
;
62
}
63
64
void
put(
int
x)
65
{
66
int
l=
strlen(dp[x][x][x]);
67
for
(
int
i=l-
1
;i>=
0
;i--
)
68
cout<<
dp[x][x][x][i];
69
cout<<endl<<
endl;
70
}
71
72
int
main()
73
{
74
int
i,j,k;
75
int
n;
76
init();
77
for
(i=
1
;i<=
60
;i++
)
78
{
79
for
(j=
0
;j<=i;j++
)
80
{
81
for
(k=
0
;k<=j;k++
)
82
{
83
a[
0
]=
'
0
'
;
84
a[
1
]=
'
\0
'
;
85
//
cout<<i<<' '<<j<<' '<<k<<endl;
86
//
cout<<dp[i-1][j][k]<<' '<<dp[i][j-1][k]<<' '<<dp[i][j][k-1]<<endl;
87
if
(i>j&&j>=
k)
88
add(dp[i-
1
][j][k]);
89
if
(j>
k)
90
add(dp[i][j-
1
][k]);
91
if
(k>
0
)
92
add(dp[i][j][k-
1
]);
93
strcpy(dp[i][j][k],a);
94
}
95
}
96
}
97
while
(~scanf(
"
%d
"
,&
n))
98
{
99
put(n);
100
}
101
return
0
;
102
}
