最長(zhǎng)上升子序列（C++，Dilworth，貪心）-創(chuàng)新互聯(lián)

題目描述

這是一個(gè)簡(jiǎn)單的動(dòng)規(guī)板子題。

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、三元網(wǎng)絡(luò)推廣、成都微信小程序、三元網(wǎng)絡(luò)營(yíng)銷、三元企業(yè)策劃、三元品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供三元建站搭建服務(wù)，24小時(shí)服務(wù)熱線：028-86922220，官方網(wǎng)址：muchs.cn

給出一個(gè)由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 個(gè)不超過(guò) 1 0 6 10^6 106 的正整數(shù)組成的序列。請(qǐng)輸出這個(gè)序列的最長(zhǎng)上升子序列的長(zhǎng)度。

最長(zhǎng)上升子序列是指，從原序列中按順序取出一些數(shù)字排在一起，這些數(shù)字是逐漸增大的。

輸入格式

第一行，一個(gè)整數(shù) n n n，表示序列長(zhǎng)度。

第二行有 n n n 個(gè)整數(shù)，表示這個(gè)序列。

輸出格式

一個(gè)整數(shù)表示答案。

樣例 #1 樣例輸入 #1

6
1 2 4 1 3 4

樣例輸出 #1

4

提示

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

解題思路：

本題其實(shí)考察的是動(dòng)態(tài)規(guī)劃，我也試著去動(dòng)態(tài)規(guī)劃了，但emmm還是定理好用

關(guān)于Dilworth定理，舉幾個(gè)例子就明白了

最長(zhǎng)上升子序列長(zhǎng)度(<) == 最少不上升子序列數(shù)目( ≥ \geq ≥)

最長(zhǎng)不下降子序列長(zhǎng)度( ≤ \leq ≤) == 最少下降子序列數(shù)目(>)

最長(zhǎng)下降子序列長(zhǎng)度(>) == 最少不下降子序列數(shù)目( ≤ \leq ≤)

最長(zhǎng)不上升子序列長(zhǎng)度( ≥ \geq ≥) == 最少上升子序列數(shù)目(<)

還可以推廣，不只是大小關(guān)系，只要是”相反“的兩個(gè)關(guān)系就可以，但“相反”的兩個(gè)關(guān)系需要滿足三個(gè)條件

（1）自反性： a ≤ a a \leq a a≤a

（2）反對(duì)稱性： 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

正面求解上面四個(gè)例子左側(cè)的問(wèn)題不太容易，但是右邊都可以直接貪心解決

以本題為例，貪心策略如下：

創(chuàng)建一個(gè)數(shù)組，然后讀入一個(gè)元素（不是讀到數(shù)組中）

如果數(shù)組中沒(méi)有比這個(gè)元素大的元素，那么將這個(gè)元素添加到數(shù)組尾

如果有，那么尋找比這個(gè)元素大的最小元素，然后把這個(gè)元素覆蓋

這個(gè)過(guò)程不需要排序就可以實(shí)現(xiàn)，可以思考一下為什么

最后數(shù)組中元素的數(shù)目即為所求解

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;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前題目：最長(zhǎng)上升子序列（C++，Dilworth，貪心）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)于：http://muchs.cn/article4/degeoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、域名注冊(cè)、外貿(mào)建站、做網(wǎng)站、Google、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)