蓝桥杯算法训练VIP-拦截导弹

题目

题目链接

题解

Dilworth定理 + 动态规划。

第一问求最长不上升子序列长度；

第二问求最长上升子序列长度。

Dilworth定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。

链：偏序集的子集，满足其中任意两个元素（不相同）可比。

反链：偏序集的子集，满足其中任意两个元素（不相同）不可比。

偏序集的链划分使用的最少集合数，等于它的最大反链长度。

偏序集的反链划分使用的最少集合数，等于它的最大链长度。

Dilworth定理证明

即求不上升子序列的最小划分，相当于是求最小反链划分，等于最长上升子序列的长度。

本来打算证明一下来着，但是发现自己离散学的真垃圾，实在看不明白就算了。但是我还是按照自己的方法证明了一点为什么要选择最长上升子序列作为第二问的答案，证明不完整，最后证不出来了（要是证出来我就成Dilworth了），因此读者可忽略。

现在证明“最长递增子序列中的每个元素都取自不同递减子序列且递增子序列元素个数与递减子序列个数相同”：

（这里包括以下说的递增不允许相等，递减允许相等）

我们分两部分证明，只要证明出“最长递增子序列中的元素是属于不同的递减子序列”和“最长递增子序列中的元素个数等于递减子序列的个数”，即可说明“最长递增子序列中的每个元素都取自不同递减子序列且递增子序列元素个数与递减子序列个数相同”。

一、证明“最长递增子序列中的元素是属于不同的递减子序列”

反证法：

假设最长递增子序列中存在若干元素是属于同一个递减子序列中，则由于它们同属于一个递减子序列，因此具有递减的性质，但是在最长递增子序列中的元素要满足递增的性质，二者相违背，因此不存在一个递减子序列为最长递增子序列贡献多个元素。

二、证明“最长递增子序列中的元素个数等于递减子序列的个数”

假设不等于，那么存在两种情况，最长递增子序列中的元素个数大于递减子序列的个数或最长递增子序列中的元素个数小于递减子序列的个数。

我只证出大于的情况下是不满足的，未证明出小于时是不满足的。

反证法：

假设最长递增子序列中的元素个数大于递减子序列的个数，由抽屉原理可知，必然存在一个递减子序列为最长递增子序列贡献了至少两个元素，还是违背一个递减子序列只能最多贡献一个元素的要求。

代码

#include<bits/stdc++.h>
using namespace std;

int cnt, ans1, ans2;
int a[100], down[100], up[100];

int main()
{
	while(cin >> a[++ cnt]) ;
	
	for(int i = 1;i < cnt;i ++) {
		for(int j = 1;j < i;j ++) {
			down[i] = max ( down[i], (a[i]<=a[j] ? down[j]+1 : 0) );
			  up[i] = max (   up[i], (a[i]> a[j] ?   up[j]+1 : 0) );
		}
		ans1 = max ( ans1, down[i] );
		ans2 = max ( ans2,   up[i] );
	}
	cout << ans1+1 << endl << ans2+1; // !!! +1
	return 0;
}