文档章节

最长不下降子序列

B
 BlueWoods
发布于 2015/05/03 23:26
字数 305
阅读 15
收藏 0

求最长不下降子序列的长度

第一行为n,表示n个数 第二行n个数

最长不下降子序列的长度

N小于5000


1. 比较粗暴的解法,依次检查数字,用dfs检查以它开始的,至数列结束的子序列的最长长度;时间复杂度在O(n*n*n); 提交上去超时了;

2. 后来想了很久,意识到,不需要每次都计算序列的长度,用一个数组 ds[n], 保存该数字后面最长序列的长度,那么dfs到该数字的时候,就可以直接返回;这样,每个位置只需要计算一次,时间复杂度是O(N * N);

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 5000;
//bool used[MAX_N];
int nums[MAX_N];
int ds[MAX_N];

int dfs(int n, int i) {
	if(i == n) {
		return 0;
	}
	if(ds[i] > 1) {
		return ds[i];
	}

	int res = 1;

	for(int j = i + 1; j < n; j++) {
		if(nums[j] >= nums[i]) {
			res = max(res, dfs(n, j) + 1);
		}
	}

	ds[i] = res;
	return res;
}

int main(void) {
	int n;
	cin >> n;
	memset(ds, 0, sizeof(ds));
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}

	int res = 0;
	for (int i = 0; i < n; i++) {
		res = max(res, dfs(n, i));
	}

	cout << res;
	return 0;
}


© 著作权归作者所有

B
粉丝 4
博文 39
码字总数 21286
作品 0
杭州
私信 提问
动态规划之合唱队形问题

问题描述: N 位同学站成一排,音乐老师要请其中的(N-K)位同学出列,而不改变其他同学的位置,使得剩下的K位同学排成合唱队形。合唱队形要求:设K位同学从左到右 依次编号为1,2…,K,他们的...

一贱书生
2016/11/22
70
0
UVA - 10534 Wavio Sequence 【最长上升子序列变形】 好题

传送门 题意: 给定一个n个数的序列, 问其中最长的波浪序列有多长, 波浪序列的定义为 : 首先长度是奇数, 即2*n + 1, 并且前面(n + 1) 个元素严格单增 , 后面(n + 1) 个元素严格单减. 思路:...

anxdada
2018/05/04
0
0
Dilworth定理 的相关应用

讲的好的博客证明 总结一下:给定一个序列, (假定有重复数字, 没有重复的类似推导) 1:如果求每次在其中选出一个不下降子序列并将其删掉, 求删完整个序列所需要的选择子序列的次数 (相当于求...

anxdada
2018/03/29
0
0
ZOJ 1025 Wooden Sticks 【思维 + 最长下降子序列 + Dilworth定理】

传送门 // 题意: 有n个木头, 每个木头有一个长度和重量. 每次一根木头准备需要1分钟, 如果下一根木头的(l’, w’) l’ >= l, w’ >= w, 那么就不用多余准备时间, 否则准备时间加1, 问处理掉这...

anxdada
2018/03/30
0
0
动态规划算法3——最长上升子序列

今天我们要讲的是最长上升子序列(LIS)。 【题目描述】 给定N个数,求这N个数的最长上升子序列的长度。 【样例输入】 7 2 5 3 4 1 7 6 【样例输出】 4 什么是最长上升子序列? 就是给你一个...

群星纪元
04/18
6
0

没有更多内容

加载失败,请刷新页面

加载更多

从AnnotationTransactionAspect开始rushSpring事务

0. Spring 事务 with LTW 0.1. Spring 事务 With LTW的原因: Pure Proxy-base mode有缺陷,其失效原因分析及使用方法及运行机制(LoadTimeWeaverBeanDefinitionParser和 AspectJWeavingEnable......

Aruforce
13分钟前
2
0
mac 安装protobuf 2.5.0

下载安装包 目前protobuf的最新版本是3.9.1,但是hadoop等好多框架依然依赖的是2.5.0,因此,最好不要安装最新的。 https://github.com/protocolbuffers/protobuf/releases/tag/v2.5.0 编译安...

hexiaoming123
17分钟前
3
0
Qt编写自定义控件52-颜色下拉框

一、前言 这个控件写了很久了,元老级别的控件之一,开发之初主要是自己的好几个项目要用到,比如提供一个颜色下拉框设置对应的曲线或者时间颜色,视频监控项目中经常用到的OSD标签设置,这个...

飞扬青云
25分钟前
2
0
Shell脚本应用 – for、while循环语句

通过Shell脚本应用(二)学习到了if条件条件语句的使用方法等。Shell作为一种脚本编程语言,同样了包含了循环,分支等其他程序控制结构,从而能够轻松完成更加复杂、强大的功能。我们今天就来...

Linux就该这么学
30分钟前
3
0
Sqoop之导入到Hive时特殊字符导致数据变乱

问题是这样的: Sqoop从关系型数据库导入数据到Hive时,发现数据量增多了,查找之后发现是由于源数据中含义\r\t\n特殊字符的数据,这样Hive遇到之后就将其视为换行,所以导入到Hive后数据条数...

克虏伯
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部