n*******g
发帖数: 325 | 1 Given a sequence of distinct integers, your program must remove as few
elements as possible in order for the elements which are not removed to
appear in ascending order. If there is more than one way to do this, your
program must print one solution, then print the number of all solutions.
Example.
Given 1 2 3 8 10 5 6 7 12 9 11 4 0
Remove 8 10 12 4 0
Remain 1 2 3 5 6 7 9 11 (ascending)
To form an ascending sequence, you must remove at least 5 elements. There is
only one way to do it.
不太理解print the number of all solutions.难道要先找出max length of the
substring，然后再来找solution？ |
l**********1
发帖数: 415 | |
j**7
发帖数: 143 | 3 longest increase subsequence |
J*****a
发帖数: 4262 | 4 好像是复杂度nlog(n-k)？k是去除的元素数 |
c*******r
发帖数: 610 | 5 是两个数字4和0
【在 l**********1 的大作中提到】
: 没看懂为什么要remove40！
|
f********x
发帖数: 2086 | 6
大牛
【在 j**7 的大作中提到】
: longest increase subsequence
|
d********i
发帖数: 582 | |
w**2
发帖数: 8 | |
|
w*****9
发帖数: 28 | 9 longest increase subsequence is not correct? |
w*******e
发帖数: 395 | 10 f[i] represents the length of longest increasing sub-sequence which ends at
A[i].
f[i] = max{ f[k]+1, where 0<=kf[k]}
finally, go through f[i] and find the max and the # of duplicates of max.
for example:
A: 1 2 3 8 10 5 6 7 12 9 11 4 0
f: 1 2 3 4 5 4 5 6 7 7 8 4 0
Therefore, 8 is the only solution.
is
【在 n*******g 的大作中提到】
: Given a sequence of distinct integers, your program must remove as few
: elements as possible in order for the elements which are not removed to
: appear in ascending order. If there is more than one way to do this, your
: program must print one solution, then print the number of all solutions.
: Example.
: Given 1 2 3 8 10 5 6 7 12 9 11 4 0
: Remove 8 10 12 4 0
: Remain 1 2 3 5 6 7 9 11 (ascending)
: To form an ascending sequence, you must remove at least 5 elements. There is
: only one way to do it.
|
|
|
n********e
发帖数: 41 | 11 大牛！
LIS nlgn 解法 一直没懂。。。
【在 J*****a 的大作中提到】
: 好像是复杂度nlog(n-k)？k是去除的元素数
|
G*********n
发帖数: 53 | 12 longest ascending sequence， Dp 经典题吧 |
w*********r
发帖数: 279 | 13
用树状数组
【在 n********e 的大作中提到】
: 大牛！
: LIS nlgn 解法 一直没懂。。。
|
f*******r
发帖数: 976 | |
f******n
发帖数: 279 | |
h*d
发帖数: 19309 | 16 需要输出所有最短序列List>，因为可能有多个一样长的结果。
is
【在 n*******g 的大作中提到】
: Given a sequence of distinct integers, your program must remove as few
: elements as possible in order for the elements which are not removed to
: appear in ascending order. If there is more than one way to do this, your
: program must print one solution, then print the number of all solutions.
: Example.
: Given 1 2 3 8 10 5 6 7 12 9 11 4 0
: Remove 8 10 12 4 0
: Remain 1 2 3 5 6 7 9 11 (ascending)
: To form an ascending sequence, you must remove at least 5 elements. There is
: only one way to do it.
|
w******k
发帖数: 299 | |
