/* 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题目答案!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题目中的一种重要题型,通常涉及动态规划算法的应用,如最长公共子序列、最短路径等。这些题目要求学习者具备动态规划算法的基础知识。 * 1013 Counterfeit Dollar:这是一个动态规划题目,要求学习者...
《北大ACM题解》是一本专为解决POJ(Programming Online Judge)平台上的编程竞赛题目而编写的指导书籍。ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)是一项全球性的比赛,旨在...
在北大POJ初级阶段,动态规划的题目可能涵盖基础的最短路径问题、最长递增子序列、矩阵链乘法、剪枝操作等。解题报告通常会包含以下几个部分: 1. **问题描述**:明确阐述题目的具体要求,包括输入和输出格式。 2. ...
《北大POJ经典结题报告》是一份针对北京大学在线编程平台POJ的解题报告,旨在帮助学习者掌握算法和编程技巧,提升解决问题的能力。POJ(Problem Online Judge)是北大的一个在线编程竞赛系统,提供了丰富的算法题目...
北京大学在线编程平台POJ(PKU Online Judge)是许多学习算法和进行编程训练的学生们的重要实践场所。这个“北大poj解题报告”包含了作者在使用POJ平台解题过程中的学习总结和经验分享,旨在帮助软件工程专业的学生...
北京大学在线判题系统(PKU Online Judge,简称POJ)是一个为编程爱好者提供在线编程练习的平台,尤其受到ACM/ICPC(国际大学生程序设计竞赛)参赛者们的喜爱。这个压缩包“ACM 北大POJ二百多道题目解答”显然包含了...
【标题】"poj1005.zip_北大poj1005"指的是北京大学(北大)在线编程竞赛平台(POJ,Problem Set)上的第1005号算法问题的压缩包资源。这个压缩包可能包含了该问题的题目描述、输入输出样例、数据限制以及提交代码的...
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
北大POJ1159-Palindrome
北大POJ1837-Balance
【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...
北大POJ第1005题答案(C语言)
【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过(AC)代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助,尤其适合初学者。POJ是许多计算机科学与技术专业...
北大POJ第1324题(C++)
北大POJ1163-The Triangle
北大POJ1080-Human Gene Functions
北京大学(Peking University, 简称PKU)的POJ(Peking University Online Judge)是一个为计算机科学爱好者和学生提供在线编程训练的平台。这个资源集合了北大POJ初级阶段的所有题目,包含已通过(Accepted, AC)的...
2. **动态规划**:解题报告中可能会包含一些经典的动态规划问题,如背包问题、矩阵链乘法、最长公共子序列等,这些都是ACM竞赛中常见的动态规划应用场景。 3. **贪心策略**:在解决一些特定问题时,贪心算法能提供...