題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1502
題目大意：找出總的滿足條件的字符串?dāng)?shù),num(a)=num(b)=num(c)且任何前綴均滿足num(a)>=num(b)>=num(c)
解題思路：用dp[i][j][k]表示a取i個,b取j個,c取k個的狀態(tài)下最多有多少種滿足條件的情況,容易推得狀態(tài)轉(zhuǎn)移方程如下：
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時)
根據(jù)該狀態(tài)轉(zhuǎn)移方程即可輸出最后的結(jié)果dp[n][n][n]
因為本題的數(shù)據(jù)結(jié)果比較大，所以還需要用到高精度，對不會用java的人就只能手敲一個大數(shù)相加了。。。
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
//
從加數(shù)開始一位一位訪問
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
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
