UC知道ACM求解3
来源：百度知道 编辑：UC知道 时间：2024/06/14 21:24:05
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
3456
3546
3526
0001
100000101
0
Sample Output
3,4,5,6
35,46
3,5,26
0001
100,000101
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
3456
3546
3526
0001
100000101
0
Sample Output
3,4,5,6
35,46
3,5,26
0001
100,000101
如果只是求最末尾的最小值，则本题是简单的DP。
然而如果加上要求前面的尽可能的大，则本题又好像不满足动态规划的要求，因为单纯DP一遍最后一个样例可能是1,00000101。
分析题目，首先是要最末尾的值最小，则一遍正向DP即可解决。
当末尾的值固定时，要使得前面的值最大，则满足反向DP的要求。
注意的是，0可以直接和其后的串合并。
void dp()
{
int i,j;
bks[0]=0;
n=strlen(sts);
for (i=1;i<n;++i)
{
bks=0;
for (j=1;j<=i;++j)
{
if (asmall(bks[j-1],j,j,i+1)&&bsmall(j,i+1,bks,i+1))
bks=j;
}
}
}
void dp2()
{
int t=bks[n-1];
dps[t]=n;
int i,j;
for (i=t-1;i>=0;--i)
{
if (sts=='0')
dps=dps[i+1];
else
{
dps=i;
for (j=i+1;j<=t;++j)
if (asmall(i,j,j,dps[j])&&asmall(i,dps,i,j))
dps=j;
}
}
}