轉載請注明出處：優 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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
