`

【最长递增子序列O(nlgn)算法】HDU 1025

阅读更多
http://acm.hdu.edu.cn/showproblem.php?pid=1025

很难说清楚,自己模拟几下就会慢慢明白,模板题
求的是最长递增子序列的长度


#include <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 500005

int v[M];

int main()
{
	int n, i, tv, x, cc = 1, top;
	while (~scanf ("%d", &n))
	{
		memset (v, 0, sizeof(v));
		for (i = 0; i < n; i++)
		{
			scanf ("%d%d", &x, &tv);
			v[x-1] = tv;
		}
	/********************模板********************/
		top = 0;
		for (i = 0; i < n; i++)
		{
			int *p = lower_bound (v, v+top, v[i]);
			if (p - v == top)
				++top;
			*p = v[i];
		}
	/********************模板********************/
		printf ("Case %d:\n", cc++);
		if (top <= 1)
			printf ("My king, at most %d road can be built.\n\n", top);
		else
			printf ("My king, at most %d roads can be built.\n\n", top);
	}
    return 0;
}
1
6
分享到:
评论

相关推荐

    最长上升子序列nlgn源码

    输入序列,求最长上升子序列的长度,算法复杂度nlgn

    单调递增子序列

    最长单调递增子序列,运行时间为O(nlgn),为算法导论上的算法

    电路布线 (O(nlgn)的算法)

    最长上升子序列问题在计算机科学中是被广泛研究的,其求解算法也具有O(nlgn)的时间复杂度。在这里,作者可能利用LIS的思路来寻找电路元件之间的最优连接顺序,从而降低布线的交叉和复杂性。 总的来说,这三个PDF...

    最大连续子序列和

    这个解法的时间复杂度为 O(NlgN),因为我们需要对数组进行分治,并且对每一个子数组进行计算连续子序列和的操作。 解法 3:O(N)解法 这个解法是最优的解法,它只需要 O(N)的时间。思路是遍历数组中的每一个元素,...

    算法分析与设计常见算法思想.pdf

    它的基本思想是先使每个子序列有序,然后使子序列段间有序。 3. 快速排序:是一种交换类排序,时间复杂度为O(nlgn)。它的基本思想是将要排序的数据分割成独立的两部分,然后再按此方法对这两部分数据分别进行快速...

    An O(ND) Difference Algorithm

    Myers提出,主要解决两个序列之间的最长公共子序列(Longest Common Subsequence, LCS)问题以及最小编辑脚本(Shortest Edit Script, SES)问题。在计算机科学领域,LCS问题和SES问题是相互对偶的问题,它们通常被...

    2020_算法XD.pdf

    - 在动态规划用于解决最长公共子序列问题的递归关系中,c[i,j]代表x[1..i]和y[1..j]的最长公共子序列的长度。 通过这些知识点的解释,我们可以对算法领域中一些基本概念和经典问题有一个系统的认识。这些内容是...

    3种方法求 最大连续子序列和

    解法1—O(N^2)解法 解法2—O(NlgN)解法 解法3—O(N)解法 可以直接在记事本运行

    1987年对比算法论文

    此算法旨在解决两个序列A和B之间的最长公共子序列(LCS)问题,同时计算将一个序列转换为另一个序列所需的最短编辑脚本。Myers通过将问题映射到编辑图中的最短路径问题上,发展出了一种时间复杂度和空间复杂度均为O...

    算法导论答案pdf清晰版

    文档建议,在归并排序中使用插入排序作为子程序来优化小规模输入的处理,从而提高整体算法的运行效率。 ### 算法复杂度分析 文档中还包含了不同算法的时间复杂度对比,如`lgn`、`√n`、`n`、`nlgn`、`n^2`、`n^3`...

    算法导论上机报告.docx

    然后,解决部分是递归求解排序子序列,合并部分是将已经排序的子序列进行合并得到所要的答案,时间复杂度为θ(lgn)。 在已经排好序的基础上,对其运用二分查找算法,时间复杂度为θ(lgn)。二分查找的条件为待查的...

    算法导论课后习题答案

    文档提供了修改插入排序算法(INSERTION-SORT)的例子,以实现元素的非递增排序。具体修改是在算法的第5行,将`A[i]&gt;key`改为`A[i]。这是一个简单的代码调整,展示了如何根据需求调整基础算法的行为。 ### 5. 线性...

    归并排序最坏情况可运行jar

    归并排序并不像快速排序那样最坏情况时间复杂度变成On2,归并排序最坏情况仍然是Onlgn,大家可以看看

    数据结构和算法 算法和复杂PPT课件.pptx

    在算法分析中,复杂度通常分为几个级别:常数阶O(1)、对数阶O(lgn)、线性阶O(n)、对数线性阶O(nlgn)、平方阶O(n^2)、立方阶O(n^3)、指数阶O(2^n)和阶乘阶O(n!)等。不同的复杂度级别反映了算法在处理大规模数据时的...

    算法导论习题答案

    这说明归并排序是时间复杂度为O(nlgn)的排序算法。 #### 算法的深入理解 - **数学归纳法**:文档提到了数学归纳法,这是一种证明方法,通常用于证明涉及自然数的等式或不等式。例如,在算法复杂度证明中,数学归纳...

    《算法导论(第二版)》(中文版)

    4. 分治法:分治法是算法设计中的一种策略,将原问题分解成若干个规模较小但类似于原问题的子问题,递归解决这些子问题,然后将子问题的解组合成原问题的解。例如,快速排序算法就是一种采用分治策略的典型算法。 5...

    算法设计分析 &#40; 第3次 &#41;.doc

    7. 最长公共子序列问题中,c[i,j]表示序列x1...xi与y1...yj的最长公共子序列的长度。 8. 函数g(n)是f(n)的下界函数,意味着当n足够大时,f(n)的增长至少与g(n)相同,即|f(n)| ≥ c|g(n)|,其中c是常数。 9. 将递归...

    快速排序算法的简单实现

    快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数中任意选出一个数,将...

    算法设计与分析期末复习整理1.21

    - 动态规划的核心是最优子结构和状态转移方程,如最短路径问题、最长公共子序列等。 11. **最优子结构**: - 一个问题是动态规划问题,如果它的最优解可以由其子问题的最优解组合得出。 这些知识点构成了算法...

    C语言快速排序.pdf

    在分解步骤中,序列被划分成两个可能为空的子序列,左边的子序列中的每个元素均小于或等于主元(也称为枢轴、支点),右边的子序列中的每个元素均大于主元。在解决步骤中,通过递归调用快速排序,对子序列进行排序。...

Global site tag (gtag.js) - Google Analytics