10.导弹拦截
[NOIP1999 普及组] 导弹拦截 - 洛谷
解题思路：
1.输入的若干个整数为导弹依次发射的高度，因为系统拦截导弹的高度是依次递减的，所要求的数量本质上是在问有多少个递减的高度，如果倒过来就是求最长上升子序列的问题（注意，相邻的两个数字相等也可以，因为是不上升子序列）
2.求最长上升子序列的解法有朴素解法O（N^2）和贪心二分策略解法O（N*logN），在本专栏第九题，在此不再赘述。
3.接下来看第二问，问至少需要多少个系统能拦截所有的导弹，受制于第一问的影响，很容易得出求出一个最长不上升子序列然后标记已被导弹拦截，然后求剩下的导弹的最长不上升子序列，但是这种做法是错误的！
举个例子：7 5 4 1 6 3 2，这七个导弹中，第一轮扫掉了7 5 4 3 2，第二轮扫1，第三轮扫6，需要三个系统，但是7 5 4 1 可以用一个系统，6 3 2也同样用一个系统即可，答案为2
所以这里不能用动态规划，应该用贪心的策略来解
4.可以设置一个ans数组，来标记每个系统拦截完导弹后高度，后续的导弹在已有的系统中寻找，如果没有满足的系统，则需要再开辟一个系统，如果有的话，应该选取哪一个呢？应该选取差值最小的，这样，别的系统可以空出更多的空间来容纳高度更高一点的！
举个例子：第一个系统的目前导弹拦截高度为158 第二个为155，现在飞来的导弹高度为65，则应该用第二个拦截，这样后续飞来157高度的就可以利用第一个系统拦截，不然的话，就得又开辟一个系统！
5.最后输出ans数组的有效长度即可，为系统的个数
代码实现：O（N^2）
#include<bits/stdc++.h>
using namespace std;
int a[2010],dp[2010],ans[2010];
int main()
{
int n,num=0;
while(cin>>n)
{
a[++num]=n;
}//输入数据
for(int i=1;i<=num/2;i++)
{
swap(a[i],a[num-i+1]);
}//头尾交换，便于求解上升子序列
for(int i=1;i<=num;i++)
dp[i]=1;//初始化为1，因为本身都是一个单调递增的序列
for(int i=2;i<=num;i++)//从第二项开始遍历
{
for(int j=1;j<i;j++)//枚举第i项前面的数字
{
if(a[i]>=a[j])//如果可以以i结尾
{
dp[i]=max(dp[i],dp[j]+1);//状态转移方程
}
}
}
int max=0;
for(int i=1;i<=num;i++)//遍历以每一个数字结尾的上升子序列数
if(dp[i]>max)
max=dp[i];//求最大值
cout<<max<<endl;
int len=1;
for(int i=1;i<=num/2;i++)
{
swap(a[i],a[num-i+1]);
}//头尾交换，便于求解系统的个数
ans[1]=a[1];//初始化第一个被拦截的导弹高度
for(int i=2;i<=num;i++)//从第二个导弹的高度开始判断
{
bool flag=0;
int min=99999999,res;
for(int j=1;j<=len;j++)//在已有的系统中进行寻找
{
if(a[i]<=ans[j])//如果有这个系统可以拦截这枚导弹
{
flag=1;//打标记
if((ans[j]-a[i])<min)//找差值最小的编号
{
min=(ans[j]-a[i]);
res=j;//记录该系统的编号
}
}
}
if(flag==1)//如果可以拦截这枚导弹
ans[res]=a[i];//将这枚导弹放在离他高度最近的那个系统上
else//如果拦截不了
ans[++len]=a[i];//开辟一个新的系统，当前高度为a[i]
}
cout<<len;//长度即为系统的数量
return 0;
}代码实现：O（N*logN）
#include<bits/stdc++.h>
using namespace std;
int a[100010],dp[100010],ans[100010];
int main()
{
int n,num=0;
while(cin>>n)
{
a[++num]=n;
}//输入数据
for(int i=1;i<=num/2;i++)
{
swap(a[i],a[num-i+1]);
}//头尾交换，便于求解上升子序列
int len=1;
dp[1]=a[1];//将第一个数字设置为上升长度1
for(int i=2;i<=num;i++)//从第二项开始遍历
{
if(a[i]>=dp[len])//如果当前项大于等于此时的上升序列最后一个数
dp[++len]=a[i]; //长度加1，表示又多了一个
else
{
int high=len,low=0,mid;//否则设置二分查找的区间
while(low<high)
{
mid=(low+high)/2;
if(dp[mid]>a[i])
high=mid;
else
low=mid+1;
}
dp[low]=min(dp[low],a[i]);//更新末尾数字
}
}
cout<<len<<endl;
len=1;
for(int i=1;i<=num/2;i++)
{
swap(a[i],a[num-i+1]);
}//头尾交换，便于求解系统的个数
ans[1]=a[1];//初始化第一个被拦截的导弹高度
for(int i=2;i<=num;i++)//从第二个导弹的高度开始判断
{
bool flag=0;
int min=99999999,res;
for(int j=1;j<=len;j++)//在已有的系统中进行寻找
{
if(a[i]<=ans[j])//如果有这个系统可以拦截这枚导弹
{
flag=1;//打标记
if((ans[j]-a[i])<min)//找差值最小的编号
{
min=(ans[j]-a[i]);
res=j;//记录该系统的编号
}
}
}
if(flag==1)//如果可以拦截这枚导弹
ans[res]=a[i];//将这枚导弹放在离他高度最近的那个系统上
else//如果拦截不了
ans[++len]=a[i];//开辟一个新的系统，当前高度为a[i]
}
cout<<len;//长度即为系统的数量
return 0;
}