解析见代码

/*先讲一下思路：
 本题来源于Noip1999(启蒙域A1260)
 原题可以用O(n^2)算法过，但本题需要用O(nlogn)
  原本的动态规划算法显然是不够的
  最多能拦截几枚导弹，本质上就是一个最长不上升序列的长度（反正只有一套）（不一定连续）
  需要配备几套系统，本质上就是一个最长上升序列的长度（高出去的要重新配备一套） 
  理论存在，实践开始！ 
 */ 
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int f[N];  //f数组存储的是最长不上升序列（注意不是子序列） 
int g[N];  //g数组存储的是最长上升序列（注意不是子序列）
int h[N];  //h数组存储导弹的高度  
int n;//n纯粹一个过程量，循环输入用的，可以优化 
int main() {
	while (cin >> h[++ n]);//这里之所以使用++n而非n++,是因为n要从1开始（当然如果你初始化n=1，那么就用n++） 
	n--; 
	int res = 1, cnt = 1;//res和cnt的用法一致，只不过为区分用处，所以用了不同的名字 
	f[1] = g[1] = h[1];//初始化 
	for (int i = 2; i <= n; i ++ ) {//请注意，因为前面已经有一步n--的操作，所以这里的n实质上是n-1,由于已经初始化f,g,h数组的第一项一致，所以只需要从2开始 
		if (h[i] <= f[res]) f[++ res] = h[i];//若出现不大于(即不上升子序列的下一项）则自动补入 
		else{
			int k = upper_bound(f + 1, f + res + 1, h[i], greater<int>()) - f;
			/*如果导弹的高度已经超出范围，那么就在已求出范围用upper_bound函数寻找
			第一个<高度的，选择拦截更高的导弹，从而给出更大限度的发挥空间*/ 
			f[k] = h[i];//根据地址锁定  
		}
		if (h[i] > g[cnt]) g[++ cnt] = h[i];//g数组同理，只不过加不加greater看情况 
		else{
			int k = lower_bound(g + 1, g + cnt + 1, h[i]) - g;
			g[k] = h[i];
		}
	}
	printf("%d\n%d\n", res, cnt);//输出 
	return 0;
}
//代码来自CSDN,注释是本人写的 




/*附加样例分析：
第一步，先统一第1项高度为h[1]=389
第二步，满足207<=389(即f[1])，故f[2](即f[++1])=207,res=2;
		不满足207>389,查找后得k=1,207替换389;
第三步，满足155<=207，故f[3]=155,res=3;
		不满足155>207,查找后得k=1,155替换207;
第四步，不满足300>=155,查找后得k=2,300替换207;
		满足300>155,cnt=2
		……
以此类推，
得res=6,拦截的6枚分别为389,300,299,170,158,65
cnt=2,需要配备初始射程为389,300的两套发射系统
*/

代码:

#include<cstdio>					//scanf / printf
#include<algorithm>					//lower_bound
#include<functional>				//greater_equal
#include<bits/stdc++.h>
using namespace std;
int a,f1[100005],f2[100005],cnt1=-1,cnt2=-1;//f1 存最长上升子序列f2 存最长不上升子序列
int main(){
	while(scanf("%d",&a)==1){//因为导弹个数不确定，所以用while输入
		if(cnt1==-1 || f1[cnt1]<a)f1[++cnt1]=a;//如果序列为空 or 这个数可以直接放在f1末尾,直接插入
		else *lower_bound(f1,f1+cnt1+1,a)=a;//否则替换掉 lower_bound 的位置的数
		if(cnt2==-1||f2[cnt2]>=a)f2[++cnt2]=a;//如果序列为空 or 这个数可以直接放在f2末尾,直接插入
		else *lower_bound(f2,f2+cnt2+1,a,greater_equal<int>())=a;//否则，替换掉 lower_bound 的位置的数 
		//因为 f2 逆序，所以需要传一个 cmp
		//cmp的第二个参数为 lower_bound 待查找值
		//此时 lower_bound 返回第一个 cmp(a,b)==false 的位置
		//greater_equal 为 >=的仿函数形式(cmp)
		//如果是正常函数就不用加括号
	}
	cout<<cnt2+1<<endl<<cnt1+1;
	return 0;	//结束！
}

lower_bound 与 upper_bound 详解与示例:

基本概念:

lower_bound 和 upper_bound 是 C++ 标准库中的算法（定义在 头文件中），用于在‌有序序列‌中快速查找元素的边界位置。它们基于二分查找实现，时间复杂度为 ‌O(log n)‌。

函数定义与参数:

// lower_bound: 返回第一个 >= val 的元素位置
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& val);

// upper_bound: 返回第一个 > val 的元素位置
template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& val);

参数：

first, last: 定义搜索范围的迭代器区间 [first, last)。

val: 要查找的目标值。

可选的第四个参数 comp: 自定义比较函数（如降序序列）。

返回值‌：

指向目标位置的迭代器。若序列中所有元素均小于 val（对于 lower_bound）或小于等于 val（对于 upper_bound），则返回 last。

函数：          返回						示例序列 [1,2,3,3,5] 查找 3
lower_bound 	第一个 ‌≥‌ val 的元素位置 	指向第一个 3（索引 2）
upper_bound 	第一个 ‌>‌ val 的元素位置 	指向 5（索引 4）

示例：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
	std::vector<int> v = {1, 2, 3, 3, 5};
	int val = 3;
	
	// lower_bound 查找第一个 >= val 的元素
	auto lb = std::lower_bound(v.begin(), v.end(), val);
	cout << "lower_bound at index: " << (lb - v.begin()) << std::endl; // 输出 2
	
	// upper_bound 查找第一个 > val 的元素
	auto ub = std::upper_bound(v.begin(), v.end(), val);
	cout << "upper_bound at index: " << (ub - v.begin()) << std::endl; // 输出 4
	
	// 计算 val 的出现次数：upper_bound - lower_bound
	int count = ub - lb;
	cout << "Number of " << val << ": " << count << std::endl; // 输出 2
	
	return 0;
}

本题解只把原题过了，不过拓展部分

思路

比赛原题只用 dp 就能做出。

第二问也用 dp，求最长不上升序列

歹马（100WA）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N],dp1[N],mx,n = 1,mn,dp2[N];// 注：mn 不是 min，只是一个变量名。作用和 mx 一样
int main(int argc, char **argv){
	while (cin >> a[n])	n++;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j < i;j++){
			if (a[i] <= a[j])	dp1[i] = max(dp1[i],dp1[j] + 1);
			if (a[i] > a[j])	dp2[i] = max(dp2[i],dp2[j] + 1);
		}
		mx = max(mx,dp1[i]);
		mn = max(mn,dp2[i]);
	}
	printf("%d\n%d",mx,mn + 1);
	return 0;
}