最长上升子序列(C++,Dilworth,贪心)-创新互联

题目描述

这是一个简单的动规板子题。

成都创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都网站制作、网站设计、三元网络推广、成都微信小程序、三元网络营销、三元企业策划、三元品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;成都创新互联为所有大学生创业者提供三元建站搭建服务,24小时服务热线:028-86922220,官方网址:www.cdcxhl.com

给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指,从原序列中按顺序取出一些数字排在一起,这些数字是逐渐增大的。

输入格式

第一行,一个整数 n n n,表示序列长度。

第二行有 n n n 个整数,表示这个序列。

输出格式

一个整数表示答案。

样例 #1 样例输入 #1
6
1 2 4 1 3 4
样例输出 #1
4
提示

分别取出 1 1 1、 2 2 2、 3 3 3、 4 4 4 即可。

解题思路:

本题其实考察的是动态规划,我也试着去动态规划了,但emmm还是定理好用

关于Dilworth定理,举几个例子就明白了

最长上升子序列长度(<) == 最少不上升子序列数目( ≥ \geq ≥)

最长不下降子序列长度( ≤ \leq ≤) == 最少下降子序列数目(>)

最长下降子序列长度(>) == 最少不下降子序列数目( ≤ \leq ≤)

最长不上升子序列长度( ≥ \geq ≥) == 最少上升子序列数目(<)

还可以推广,不只是大小关系,只要是”相反“的两个关系就可以,但“相反”的两个关系需要满足三个条件

(1)自反性: a ≤ a a \leq a a≤a

(2)反对称性: a ≤ b , b ≤ a , a = b a \leq b, b\leq a, a = b a≤b,b≤a,a=b

(3)传递性: a ≤ b , b ≤ c , a ≤ c a \leq b, b \leq c, a \leq c a≤b,b≤c,a≤c

正面求解上面四个例子左侧的问题不太容易,但是右边都可以直接贪心解决

以本题为例,贪心策略如下:

创建一个数组,然后读入一个元素(不是读到数组中)

如果数组中没有比这个元素大的元素,那么将这个元素添加到数组尾

如果有,那么寻找比这个元素大的最小元素,然后把这个元素覆盖

这个过程不需要排序就可以实现,可以思考一下为什么

最后数组中元素的数目即为所求解

AC代码如下

#include#includeusing namespace std;

vectornot_upper_arr;

int main() {int n, num;
	cin >>n;
	for (int i = 0; i< n; i++) {cin >>num;
		if (not_upper_arr.empty() || not_upper_arr.back()< num) not_upper_arr.push_back(num);
		else {	size_t j = not_upper_arr.size();
			while (--j< not_upper_arr.size() && not_upper_arr[j] >= num);
			not_upper_arr[++j] = num;
		}
	}

	cout<< not_upper_arr.size();
	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻名称:最长上升子序列(C++,Dilworth,贪心)-创新互联
网站URL:http://pwwzsj.com/article/degeoe.html