传送门 ↬\looparrowright

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于 3000030000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入描述

11 行，若干个整数（个数 ≤100000≤100000）。

输出描述

22 行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

示例1

输入
389 207 155 300 299 170 158 65
输出
6
2

分析

首先明确，当且仅当一颗炮弹的高度和导弹相等时，导弹可被拦截。
设第 ii 颗导弹的高度为 h[i]h[i]。
由题意，能够用一套拦截的导弹，其高度构成一个不上升序列。因此，一套系统最多能拦截的数量是数组 hh 中最长不上升子序列。
对于第二个问题，考虑每一套设备分管一段 hh 中的独立的不上升子序列（各个子序列在 hh 中的下标没有交集，所有子序列的并集为 hh），由 Dilworth\text{Dilworth} 定理，不上升子序列的最小划分数为 hh 的最长上升子序列长度。
综上所述，题目要求输出 hh 的最长不上升子序列长度和最长上升子序列长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define N 100003
using namespace std;
int n;
int dp[N];
int h[N];
int main()
{
	int i;
	/*****************
	*                *
	*  略显奇怪的输入  *
	*                *
	*****************/  
	n=1;
	while(~scanf("%d",h+n)) n++;
	n--;
	//此时dp[i]代表不上升子序列长度为i时，末尾元素的最优值
	dp[1]=h[1];
	int ans1=1;
	for(i=2;i<=n;i++)
	{
		//upper_bound设置比较为>，找第一个小于等于h[i]的数
		if(h[i]<=dp[ans1]) dp[++ans1]=h[i];
		else *upper_bound(dp+1,dp+ans1+1,h[i],greater<int>())=h[i];
	}
	memset(dp,0,sizeof(dp));
	int ans2=1;
	//此时dp[i]代表上升子序列长度为i时，末尾元素的最优值
	dp[1]=h[1];
	for(i=2;i<=n;i++)
	{
		//lower_bound设置比较为<，找第一个大于等于h[i]的数
		if(h[i]>dp[ans2]) dp[++ans2]=h[i];
		else *lower_bound(dp+1,dp+ans2+1,h[i])=h[i];
	}
	cout<<ans1<<endl<<ans2<<endl;
	return 0;
}