题意：略。
思路：进行两次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
}
