題意：略。
思路：進行兩次dp。
第一次dp從前向后，用dp[x]表示從第x位向前dp[x]位可構成一個數字，且與前面的數組符合題意要求。最后求的dp[n]即為最后一個數字的長度。
而題目還有要求，所有解中輸出前面數字最大的一個。因此還需要進行一次dp，從后向前。
具體看代碼吧，當初也是看別人代碼才看懂的。
?
1
#include<stdio.h>
2
#include<
string
.h>
3
char
num[
85
];
4
int
dp[
85
], n;
5
bool
judge(
int
st1,
int
len1,
int
st2,
int
len2)
6
{
7
while
(num[st1] ==
'
0
'
&& len1) st1++, len1--
;
8
while
(num[st2] ==
'
0
'
&& len2) st2++, len2--
;
9
if
(len1 < len2)
return
1
;
10
else
if
(len1 > len2)
return
0
;
11
else
12
{
13
for
(
int
i =
0
; i < len1; i++
)
14
{
15
if
(num[st1+i] < num[st2+i])
return
1
;
16
if
(num[st1+i] > num[st2+i])
return
0
;
17
}
18
}
19
return
0
;
20
}
21
void
print(
int
pos)
22
{
23
if
(pos > n)
return
;
24
if
(pos !=
1
) printf(
"
,
"
);
25
for
(
int
i = pos; i < pos + dp[pos]; i++
)
26
printf(
"
%c
"
, num[i]);
27
print(pos +
dp[pos]);
28
}
29
int
main()
30
{
31
while
(~scanf(
"
%s
"
, num +
1
) && strcmp(num +
1
,
"
0
"
))
32
{
33
n = strlen(num +
1
);
34
dp[
1
] =
1
;
35
for
(
int
i =
2
; i <= n; i++
)
36
{
37
dp[i] =
i;
38
for
(
int
j = i -
1
; j >=
1
; j--
)
39
if
(judge(j - dp[j] +
1
, dp[j], j +
1
, i -
j))
40
{
41
dp[i] = i -
j;
42
break
;
43
}
44
}
45
int
pos = n - dp[n] +
1
;
46
dp[pos] =
dp[n];
47
for
(
int
i = pos -
1
; i >=
1
; i--
)
48
{
49
if
(num[i] ==
'
0
'
)
50
{
51
dp[i] = dp[i+
1
] +
1
;
52
continue
;
53
}
54
for
(
int
j = pos; j > i; j--
)
55
if
(judge(i, j -
i, j, dp[j]))
56
{
57
dp[i] = j -
i;
58
break
;
59
}
60
}
61
print(
1
);
62
printf(
"
\n
"
);
63
}
64
return
0
;
65
}
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
