`

【最长上升子序列】北大 POJ 1631 Bridging signals

阅读更多

 

/* 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题目答案!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大量解题代码"指的是北京大学在线编程平台POJ上的一系列算法题目解决方案的集合。这些代码通常由ACM(国际大学生程序设计竞赛)参赛者或爱好者编写,旨在帮助学习者理解并解决各类算法问题,提高...

    北京大学poj题目类型分类

    动态规划是POJ题目中的一种重要题型,通常涉及动态规划算法的应用,如最长公共子序列、最短路径等。这些题目要求学习者具备动态规划算法的基础知识。 * 1013 Counterfeit Dollar:这是一个动态规划题目,要求学习者...

    北大acm题解(poj题目分析)

    《北大ACM题解》是一本专为解决POJ(Programming Online Judge)平台上的编程竞赛题目而编写的指导书籍。ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)是一项全球性的比赛,旨在...

    北大POJ初级-动态规划

    在北大POJ初级阶段,动态规划的题目可能涵盖基础的最短路径问题、最长递增子序列、矩阵链乘法、剪枝操作等。解题报告通常会包含以下几个部分: 1. **问题描述**:明确阐述题目的具体要求,包括输入和输出格式。 2. ...

    北大POJ经典结题报告

    《北大POJ经典结题报告》是一份针对北京大学在线编程平台POJ的解题报告,旨在帮助学习者掌握算法和编程技巧,提升解决问题的能力。POJ(Problem Online Judge)是北大的一个在线编程竞赛系统,提供了丰富的算法题目...

    北大poj解题报告

    北京大学在线编程平台POJ(PKU Online Judge)是许多学习算法和进行编程训练的学生们的重要实践场所。这个“北大poj解题报告”包含了作者在使用POJ平台解题过程中的学习总结和经验分享,旨在帮助软件工程专业的学生...

    ACM 北大POJ二百多道题目解答

    北京大学在线判题系统(PKU Online Judge,简称POJ)是一个为编程爱好者提供在线编程练习的平台,尤其受到ACM/ICPC(国际大学生程序设计竞赛)参赛者们的喜爱。这个压缩包“ACM 北大POJ二百多道题目解答”显然包含了...

    poj1005.zip_北大poj1005

    【标题】"poj1005.zip_北大poj1005"指的是北京大学(北大)在线编程竞赛平台(POJ,Problem Set)上的第1005号算法问题的压缩包资源。这个压缩包可能包含了该问题的题目描述、输入输出样例、数据限制以及提交代码的...

    poj经典动态规划题目解题报告

    poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...

    北大POJ1159-Palindrome

    北大POJ1159-Palindrome

    北大POJ1837-Balance

    北大POJ1837-Balance

    北大poj JAVA源码

    【北大POJ JAVA源码】是一系列用于解决北京大学在线编程平台(POJ)问题的Java程序集合。这个压缩包中的代码资源,对于学习Java编程、算法设计和优化以及熟悉在线编程竞赛有着重要的参考价值。POJ是北京大学面向全国...

    北大POJ第1005题答案.c

    北大POJ第1005题答案(C语言)

    北大POJ初级-基本算法

    【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过(AC)代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助,尤其适合初学者。POJ是许多计算机科学与技术专业...

    北大POJ 1324.cpp

    北大POJ第1324题(C++)

    北大POJ1163-The Triangle

    北大POJ1163-The Triangle

    北大POJ1080-Human Gene Functions

    北大POJ1080-Human Gene Functions

    北大POJ初级-所有题目AC代码+解题报告

    北京大学(Peking University, 简称PKU)的POJ(Peking University Online Judge)是一个为计算机科学爱好者和学生提供在线编程训练的平台。这个资源集合了北大POJ初级阶段的所有题目,包含已通过(Accepted, AC)的...

    北京大学_POJ_ACM解题报告

    2. **动态规划**:解题报告中可能会包含一些经典的动态规划问题,如背包问题、矩阵链乘法、最长公共子序列等,这些都是ACM竞赛中常见的动态规划应用场景。 3. **贪心策略**:在解决一些特定问题时,贪心算法能提供...

Global site tag (gtag.js) - Google Analytics