1239 Increasing Sequences

124 阅读 0 评论 82 点赞

我是靠谱客的博主殷勤缘分，这篇文章主要介绍1239 Increasing Sequences，现在分享给大家，希望可以做个参考。

Increasing Sequences

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 482		Accepted: 162

Description
Given a string of digits, insert commas to create a sequence of strictly increasing numbers so as to minimize the magnitude of the last number. For this problem, leading zeros are allowed in front of a number.

Input
Input will consist of multiple test cases. Each case will consist of one line, containing a string of digits of maximum length 80. A line consisting of a single 0 terminates input.

Output
For each instance, output the comma separated strictly increasing sequence, with no spaces between commas or numbers. If there are several such sequences, pick the one which has the largest first value;if there's a tie, the largest second number, etc.

Sample Input

Sample Output

Source
East Central North America 2002

**************************************************************************************

************************************************************************************9**

Source Code

复制代码

#include <stdio.h>
#include <string.h>
#define N_MAX 81
char seqStr[N_MAX];
char d[N_MAX][N_MAX];
char res[N_MAX],resTemp[N_MAX];
int num;
bool Great(int start1,int len1,int start2,int len2)
{
while(len1 > 0 && seqStr[start1] == '0')
{
len1--;
start1++;
}
while(len2 > 0 && seqStr[start2] == '0')
{
len2--;
start2++;
}
if(len1 > len2)
return true;
else if(len1 == len2)
{
while(len1 > 0)
{
if(seqStr[start1] > seqStr[start2])
return true;
else if(seqStr[start1] < seqStr[start2])
return false;
else
{
start1++;
start2++;
len1--;
}
}
return false;
}
else
return false;
}
void GetResult(int idx,int len,int numTemp)
{
int i,j;
if(idx == len)
{
if(num == 0)
{
resTemp[numTemp] = len;
num = numTemp + 1;
memcpy(res,resTemp,num);
}
else
{
bool best = false;
resTemp[numTemp] = len;
for(i = numTemp,j = num - 1 ; i >= 0 && j >= 0 ; i--,j--)
{
if(resTemp[i] > res[j])
best = true;
if(resTemp[i] == res[j])
continue;
break;
}
if(best == true)
{
num = numTemp + 1;
memcpy(res,resTemp,num);
}
}
}
else
{
resTemp[numTemp] = len;
for(i = 1 ; i <= d[idx][len] ; i++)
{
if(d[idx-len][i] == 0)
continue;
GetResult(idx-len,i,numTemp+1);
}
}
}
void DP()
{
int i,j,t,prev;
bool bGreat;
int len = strlen(seqStr + 1) + 1;
d[1][1] = 1;
for(i = 2 ; i < len ; i++)
{
d[i][i] = 1;
for(j = 1 ; j < i ; j++)
{
prev = i - j;
t = j;
while(t < prev && seqStr[prev - t] == '0')
t++;
for( ; t > 0 ; t--)
{
if(d[prev][t] == 0)
continue;
if(Great(i - j + 1,j,prev - t + 1,t))
{
bGreat = true;
break;
}
}
if(bGreat == true)
d[i][j] = t;
else
d[i][j] = 0;
}
}
prev = len - 1;
for(i = 1 ; i < len ; i++)
{
if(d[prev][i] > 0)
break;
}
j = i;
while(j < len && seqStr[prev - j] == '0')
j++;
num = 0;
for( ; i <= j ; i++)
GetResult(prev,i,0);
prev = 1;
for(i = num - 1 ; i > 0 ; i--)
{
j = prev + res[i];
for( ; prev < j ; prev++)
printf("%c",seqStr[prev]);
printf(",");
}
j = prev + res[i];
for( ; prev < j ; prev++)
printf("%c",seqStr[prev]);
printf("/n");
}
int main()
{
//freopen("test.txt","r",stdin);
while(scanf("%s",seqStr + 1) != EOF)
{
if(strlen(seqStr + 1) == 1 && seqStr[1] == '0')
break;
DP();
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <stdio.h>
#include <string.h>
#define N_MAX 81
char seqStr[N_MAX];
char d[N_MAX][N_MAX];
char res[N_MAX],resTemp[N_MAX];
int num;
bool Great(int start1,int len1,int start2,int len2)
{
while(len1 > 0 && seqStr[start1] == '0')
{
len1--;
start1++;
}
while(len2 > 0 && seqStr[start2] == '0')
{
len2--;
start2++;
}
if(len1 > len2)
return true;
else if(len1 == len2)
{
while(len1 > 0)
{
if(seqStr[start1] > seqStr[start2])
return true;
else if(seqStr[start1] < seqStr[start2])
return false;
else
{
start1++;
start2++;
len1--;
}
}
return false;
}
else
return false;
}
void GetResult(int idx,int len,int numTemp)
{
int i,j;
if(idx == len)
{
if(num == 0)
{
resTemp[numTemp] = len;
num = numTemp + 1;
memcpy(res,resTemp,num);
}
else
{
bool best = false;
resTemp[numTemp] = len;
for(i = numTemp,j = num - 1 ; i >= 0 && j >= 0 ; i--,j--)
{
if(resTemp[i] > res[j])
best = true;
if(resTemp[i] == res[j])
continue;
break;
}
if(best == true)
{
num = numTemp + 1;
memcpy(res,resTemp,num);
}
}
}
else
{
resTemp[numTemp] = len;
for(i = 1 ; i <= d[idx][len] ; i++)
{
if(d[idx-len][i] == 0)
continue;
GetResult(idx-len,i,numTemp+1);
}
}
}
void DP()
{
int i,j,t,prev;
bool bGreat;
int len = strlen(seqStr + 1) + 1;
d[1][1] = 1;
for(i = 2 ; i < len ; i++)
{
d[i][i] = 1;
for(j = 1 ; j < i ; j++)
{
prev = i - j;
t = j;
while(t < prev && seqStr[prev - t] == '0')
t++;
for( ; t > 0 ; t--)
{
if(d[prev][t] == 0)
continue;
if(Great(i - j + 1,j,prev - t + 1,t))
{
bGreat = true;
break;
}
}
if(bGreat == true)
d[i][j] = t;
else
d[i][j] = 0;
}
}
prev = len - 1;
for(i = 1 ; i < len ; i++)
{
if(d[prev][i] > 0)
break;
}
j = i;
while(j < len && seqStr[prev - j] == '0')
j++;
num = 0;
for( ; i <= j ; i++)
GetResult(prev,i,0);
prev = 1;
for(i = num - 1 ; i > 0 ; i--)
{
j = prev + res[i];
for( ; prev < j ; prev++)
printf("%c",seqStr[prev]);
printf(",");
}
j = prev + res[i];
for( ; prev < j ; prev++)
printf("%c",seqStr[prev]);
printf("/n");
}
int main()
{
//freopen("test.txt","r",stdin);
while(scanf("%s",seqStr + 1) != EOF)
{
if(strlen(seqStr + 1) == 1 && seqStr[1] == '0')
break;
DP();
}
return 0;
}

复制代码3,4,5,6 35,46 3,5,26 0001 100,000101
```
1
2
3
4
5
3,4,5,6
35,46
3,5,26
0001
100,000101
```
复制代码3456 3546 3526 0001 100000101 0
```
1
2
3
4
5
6
3456
3546
3526
0001
100000101
0
```