一、问题描述

P1020 [NOIP1999 提高组] 导弹拦截

二、问题简析

该题要我们求两个问题：

• 1、不上升子序列的最大长度
• 2、不上升子序列的最少个数

利用 \(Dilworth\) 定理，我们得到不上升子序列的最少个数等于上升子序列的最大长度。

现在，就是求这两个问题：

• 1、不上升子序列的最大长度
• 2、上升子序列的最大长度

类比最长上升子序列，我们可以得到求最长不上升子序列的方法。与最长上升子序列不同点：

• 1、\(dp[i]\) 都初始化为 \(0\)
• 2、\(dp[i]\) 是非升序，所以要用 *upper_bound(dp1, dp1 + cnt, A[i], greater<int>()) = A[i] 更新
• 3、最终结果为 lower_bound(dp1, dp1 + cnt, 0, greater<int>()) - dp1

AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 1e5 + 3;
const int INF = 1e8;
int dp1[MAX], dp2[MAX], A[MAX];

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	int num, cnt = 0;
	while (cin >> num)
		A[cnt++] = num;
		
	fill(dp2, dp2 + cnt, INF);
	for (int i = 0; i < cnt; i++)
	{
		*upper_bound(dp1, dp1 + cnt, A[i], greater<int>()) = A[i];
		
		*lower_bound(dp2, dp2 + cnt, A[i]) = A[i];
	}
	cout << lower_bound(dp1, dp1 + cnt, 0, greater<int>()) - dp1 << endl;
	cout << lower_bound(dp2, dp2 + cnt, INF) - dp2 << endl;
	
	return 0;
}

完