最长上升子序列（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://cdkjz.cn/article/degeoe.html