概述
Increasing Sequences
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 1532 | Accepted: 643 |
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
Source
East Central North America 2002
先用dp[i][j] 求出前i个最后一个是从 j----i 是否存在并且记录一下他是从那些值来的
所有dp都求出来之后
从后向前找 找到最后一个最小的时候在哪里，因为有可能有前缀0，所以要把可以包含的前缀零全部包含进去考虑。
找到最后一段的位置之后，深搜，将所有的解记录下来，值得注意的是，在搜索解的过程中，并不是很好记录，解构成的是一棵树，所以要通过树的性质来记录，再将所有的解比较。
此题反应出的问题：
1.搜索时候构造最优解是要记录每一枝，但是按照之前的想法根本没有记录出所有的解
(因为每次分一枝的时候解的个数就增加了，之前的那些值都不存在了)
2.在写cmp函数的时候倒是很明确，到后面判断的时候就忘记了。很是头疼……
3.我还是会想某人，当然也知道自己真的不太招人喜欢。
解题报告：
http://hi.baidu.com/happynp/blog/item/43c4bf2d6798c433359bf73c.html
方法很省时，不好想……
最后
以上就是笑点低草丛为你收集整理的Increasing Sequence的全部内容，希望文章能够帮你解决Increasing Sequence所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复