/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://poj.org/problem?id=1631
Name : 1631 Bridging signals
Classification : 最长上升子序列
Date : Wednesday, July 11, 2012
Time Stage : half an hour
Result:
10420085 panyanyany
1631
Accepted 472K 125MS C++
1557B 2012-07-11 07:29:31
Test Data :
Review :
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (40005)
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)|1)
#define M(x, y) (((x)+(y)) >> 1)
#define DB //
int a[MAXN], order[MAXN];
int LIS(int a[], int n)
{
int i, u, l, m, len;
len = 1;
MEM(order, INF); // 找上升子序列时初始化 INF,找下降子序列时初始化为0
for (i = 0; i < n; ++i)
{
u = len;
l = 1;
while (l <= u)
{
m = (l + u) >> 1;
if (order[m] < a[i])
l = m + 1;
else
u = m - 1;
}
if (order[l] > a[i])
order[l] = a[i];
if (len < l)
len = l;
// printf("^ %d ^", l);
}
return len;
}
int main()
{
int i, n, tc;
while (scanf("%d", &tc) != EOF)
{
while (tc--)
{
scanf("%d", &n);
for (i = 0; i < n; ++i)
scanf("%d", a+i);
printf("%d\n", LIS(a, n));
}
}
return 0;
}
分享到:
相关推荐
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
ACM POJ 解题报告北大POJ 大量解题代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ1159-Palindrome
北大POJ1837-Balance
北大poj JAVA源码
北大POJ第1005题答案(C语言)
北大POJ第1324题(C++)
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
北大POJ1163-The Triangle
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
北大POJ1080-Human Gene Functions
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ初级-动态规划 解题报告+AC代码
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码