生若有余
poj 1631 Bridging signals 最长上升子序列
//
Bridging signals 1631 最长上升子序列 dp问题 2010.8.13
#include
<
iostream
>
using
namespace
std;
const
int
MAXP
=
40005
;
int
L[MAXP];
int
bSearch(
int
left,
int
right,
int
num)
{
if
(right
==
left)
return
left;
int
mid
=
(left
+
right)
/
2
;
if
(num
==
L[mid])
return
mid;
else
if
(num
>
L[mid])
{
if
(right
<
mid
+
1
)
return
mid;
else
return
bSearch(mid
+
1
,right,num);
}
else
if
(num
<
L[mid])
{
if
(left
>
mid
-
1
)
return
mid;
else
return
bSearch(left,mid,num);
}
else
return
mid;
}
int
solve(
int
n)
{
int
ans
=
0
;
int
temp
=
0
;
int
count
=
0
;
scanf(
"
%d
"
,
&
temp);
L[ans
++
]
=
temp;
n
--
;
while
(n
--
)
{
scanf(
"
%d
"
,
&
temp);
if
(temp
>
L[ans
-
1
])
L[ans
++
]
=
temp;
else
L[bSearch(
0
,ans
-
1
,temp)]
=
temp;
}
return
ans;
}
int
main(
int
argc,
char
*
argv[])
{
int
t,n;
cin
>>
t;
while
(t
--
)
{
cin
>>
n;
cout
<<
solve(n)
<<
endl;
}
return
0
;
}
posted on 2010-08-13 15:09
若余
阅读(197)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
导航
首页
新随笔
联系
聚合
管理
<
2010年8月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
统计
随笔 - 16
文章 - 0
评论 - 4
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
(16)
2010年9月 (1)
2010年8月 (14)
2009年8月 (1)
搜索
最新随笔
1. poj 1797 Heavy Transportation 最短路
2. poj 3734 Blocks 生成函数
3. poj 2348 Euclid's Game 博弈 取子
4. Poj 2153 Rank List --map / 计数排序
5. 1430 Binary Stirling Numbers 斯特灵数
6. POJ 3318 Matrix Multiplication 随机化算法
7. poj 1195 Mobile phones 二维树状数组
8. POJ 1026 Cipher
9. Poj 2785 4 Values whose Sum is 0 hash 哈希表
10. Push Botton Lock poj 3088斯特灵数
最新评论
1. re: 快速幂取模 PKU ACM 3070
评论内容较长,点击标题查看
--呢喃的歌声
2. re: poj 2085 Inversion 求逆序列[未登录]
@sdz
谢谢博主,是我理解错了。
--Klion
3. re: poj 2085 Inversion 求逆序列
评论内容较长,点击标题查看
--sdz
4. re: poj 2085 Inversion 求逆序列[未登录]
只要知道这样一个事实:一个序列的逆序唯一决定了这个序列。
楼主,对这个不是很理解,望解释。
比如
4 5 3 2 1和5 3 4 2 1的逆序数都是9,或许是我理解有问题?
--Klion
评论排行榜
1. poj 2085 Inversion 求逆序列(3)
2. 快速幂取模 PKU ACM 3070(1)
3. poj 1631 Bridging signals 最长上升子序列(0)
4. poj 3358 Period of an Infinite Binary Expansion求有理数循环节长度(0)
5. poj 2282 The Counting Problem 3252 round numbers(0)