转载请注明出处：優 YoU http://user.qzone.qq.com/289065406/blog/1300023619
提示：
动态规划，求
LIS
最大不下降子序列
O(n^2)
和
O(n*logn)
算法都能完美
AC
不懂的就去看看
LIS
的概念就会做了
我把两种算法都贴出来：
1
//
Memory Time
2
//
228K 16MS
3
4
//
O(n^2)算法
5
#include
<
iostream
>
6
using
namespace
std;
7
8
int
main(
int
i,
int
j)
9
{
10
int
n;
11
while
(cin
>>
n)
12
{
13
int
*
sq
=
new
int
[n];
14
int
*
dp
=
new
int
[n];
//
dp[i]表示以第i个位置为终点的最长不下降序列的长度
15
16
for
(i
=
0
;i
<
n;i
++
)
17
cin
>>
sq[i];
18
19
int
max_length
=
0
;
20
for
(i
=
0
;i
<
n;i
++
)
21
{
22
dp[i]
=
1
;
//
初始化dp[0]=1,其他最小值为1
23
for
(j
=
0
;j
<
i;j
++
)
24
if
(sq[j]
<
sq[i]
&&
dp[i]
<
dp[j]
+
1
)
25
dp[i]
=
dp[j]
+
1
;
26
27
if
(max_length
<
dp[i])
28
max_length
=
dp[i];
29
}
30
cout
<<
max_length
<<
endl;
31
32
delete sq,dp;
33
}
34
return
0
;
35
}
===========华丽的分割线=============
1
//
Memory Time
2
//
224K 0MS
3
4
//
O(n*logn)算法
5
#include
<
iostream
>
6
using
namespace
std;
7
const
int
inf
=
10001
;
8
9
int
binary_search(
int
ord[],
int
digit,
int
length)
//
二分法搜索digit，若str中存在digit，返回其下标
10
{
//
若不存在，返回str中比digit小的最大那个数的（下标+1）
11
int
left
=
0
,right
=
length;
12
int
mid;
13
while
(right
!=
left)
14
{
15
mid
=
(left
+
right)
/
2
;
16
if
(digit
==
ord[mid])
17
return
mid;
18
else
if
(digit
<
ord[mid])
19
right
=
mid;
20
else
21
left
=
mid
+
1
;
22
}
23
return
left;
24
}
25
26
int
main(
int
i,
int
j)
27
{
28
int
n;
29
while
(cin
>>
n)
30
{
31
int
*
sq
=
new
int
[n
+
1
];
32
int
*
ord
=
new
int
[n
+
1
];
//
对于dp[]的每一个取值k，ord[k]记录满足dp[i]=k的所有sq[i]中的最小值，即ord[k]=min{sq[i]} (dp[i]=k)
33
34
for
(i
=
1
;i
<=
n;i
++
)
35
cin
>>
sq[i];
36
37
int
max_length
=
0
;
38
ord[
0
]
=-
1
;
//
下界无穷小
39
int
len
=
1
;
//
ord的长度
40
for
(i
=
1
;i
<=
n;i
++
)
41
{
42
ord[len]
=
inf;
//
上界无穷大,指针len总是指向ord最后一个元素的后一位
43
j
=
binary_search(ord,sq[i],len);
44
if
(j
==
len)
//
sq[i]大于ord最大（最后）的元素
45
len
++
;
46
ord[j]
=
sq[i];
47
}
48
cout
<<
len
-
1
<<
endl;
//
len要减去ord[0]的长度1
49
50
delete sq,ord;
51
}
52
return
0
;
53
}
