Dilworth定理：最少的下降序列个数就等于整个序列最长上升子序列的长度

admin管理员组

文章数量:1794759

Dilworth定理：最少的下降序列个数就等于整个序列最长上升子序列的长度

概念如下：

狄尔沃斯定理_百度百科 (baidu)

本质就是找要求序列中最长的单调的子序列（不一定连续）的长度。

最长上升子序列（Longest Increasing Subsequence），简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数

假设我们有一个序列 b i，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们也可以从中得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N，但必须按照从前到后的顺序。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，我们就会得到一些上升的子序列，如(1, 7, 9), (3, 4, 8), (1, 3, 5, 8)等等，而这些子序列中最长的（如子序列(1, 3, 5, 8) ），它的长度为4，因此该序列的最长上升子序列长度为4。

下面是最长单调递增子序列长度

模板如下：

时间复杂度为O（N^2）

#include <iostream>
#include <algorithm>
using namespace std;
int a[5005], dp[5005];

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i], dp[i] = 0; //初始化
	int cnt = 1;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (a[i] <= a[j]) dp[i] = max(dp[i], dp[j] + 1);
		}
		cnt = max(cnt, dp[i]);
	}
    cout<<cnt<<endl;

	return 0;
}

代码优化：

举个例子：

现在有序列4，8，9，5，6，7，2，7求 最长上升子序列（Longest Increasing Subsequence）简称LIS，也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

一个一个元素来看，首先无疑dp[1]=4 ，然后考察8，8>4，故把8加入尾部。然后9>8，也进入尾部，这时dp数组是{4, 8, 9}。

下一个元素是5，5<9，不能塞入尾部。我们找到第一个大于等于5的元素，是8。4->8是长度为2的上升子序列，4->5也是，但是5比8更小，所以更有潜力更新后面的子序列。所以把8换成5，现在DP是{4, 5, 9}。同样的道理DP又变成{4, 5, 6}。

现在我们尝到甜头了，因为下一个元素是7，本来是没有机会进入序列的，现在却可以了。于是dp变成{4, 5, 6, 7}。注意，显然DP是递增的（两种转移都不会破坏递增性），但这并不意味着它就是所求的上升子序列，你看，下一个元素是2，它会把dp更新成{2, 5, 6, 7}，但原序列并没有一个子序列是{2, 5, 6, 7}。

最后剩一个元素7，由于我们在求严格上升的子序列，不能将它插入尾部，于是我们把7替换成7——这个元素对子序列长度没有贡献。好了，最后得到的数组长度是4，所以最长上升子序列的长度就是4 。

刚刚提到，dp是递增的，所以我们不用每次都扫描一遍数组， 而可以进行二分查找。这样，就把复杂度降到了

本文标签： Dilworth定理最少的下降序列个数就等于整个序列最长上升子序列的长度