轉(zhuǎn)載請(qǐng)注明出處：優(yōu) YoU http://user.qzone.qq.com/289065406/blog/1300023619
?
提示：
動(dòng)態(tài)規(guī)劃，求
LIS
最大不下降子序列
O(n^2)
和
O(n*logn)
算法都能完美
AC
不懂的就去看看
LIS
的概念就會(huì)做了
我把兩種算法都貼出來：
?
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個(gè)位置為終點(diǎn)的最長(zhǎng)不下降序列的長(zhǎng)度
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，返回其下標(biāo)
10
{
//
若不存在，返回str中比digit小的最大那個(gè)數(shù)的（下標(biāo)+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
];
//
對(duì)于dp[]的每一個(gè)取值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的長(zhǎng)度
40
for
(i
=
1
;i
<=
n;i
++
)
41
{
42
ord[len]
=
inf;
//
上界無窮大,指針len總是指向ord最后一個(gè)元素的后一位
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]的長(zhǎng)度1
49
50
delete sq,ord;
51
}
52
return
0
;
53
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
