【题解】「NOIP1999 普及组」导弹拦截（DP，最长不下降子序列+贪心）

本文主要是介绍【题解】「NOIP1999 普及组」导弹拦截（DP，最长不下降子序列+贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

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

389 207 155 300 299 170 158 65

【样例输出】

6
2

算法分析

本题有两个问题，先看第一问。
问题一：这套系统最多能拦截多少导弹？
假设拦截的导弹高度为 $h_1,h_2,h_3..h_k$ ，它们需要满足的关系是 $h_1\>= h_2>= h_3>= .. >= h_k$ ，这就是最长不上升子序列。

问题二：要拦截所有导弹最少要配备多少套这种导弹拦截系统
假设目前有 $m$ 套拦截系统，能够拦截的导弹最高高度为 $h_1,h_2,h_3..h_k$ ，现在有一枚导弹高度为 $H$ ，如果 $m$ 套系统都能拦截，那么选择哪一套系统呢？
选择能够拦截 $H$ 且拦截高度最小的拦截系统去拦截，把拦截高度高的留着拦截更高的导弹，这就是贪心的方法。
因此，可以使用数组 $s$ 表示每套拦截系统的高度。如果所有拦截系统都不能拦截，拦截系统就增加一套。

参考程序

#include<iostream>
using namespace std;
int a[1100],f[1100],s[1100];
int main()
{int ans=0,n=1;while(cin>>a[n])	//输入 {n++;}for(int i=1;i<n;i++)	//最长不上升子序列 {int falg=1,t=0;for(int j=i-1;j>=1;j--){if(a[j]>=a[i]){if(f[j]>t) t=f[j];falg=0;}}if(falg) f[i]=1;else f[i]=t+1;ans=max(ans,f[i]);}cout<<ans<<endl;int m=0,p;for(int i=1;i<=n;i++){int x=9999999,flag=1;for(int k=1;k<=m;k++){if(s[k]>=a[i]){if(s[k]<=x) {x=s[k];p=k;}		//选择能够拦截，且高度最小的拦截系统flag=0;}}if(flag) {m++;s[m]=a[i];}		//不能拦截就增加一套系统m++,新系统拦截高度=a[i]else s[p]=a[i];					} cout<<m<<endl;return 0;
}