1260：【例9.4】拦截导弹(Noip1999)

· · 个人记录

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

【输入】 输入导弹依次飞来的高度。 【输出】 第一行：最多能拦截的导弹数； 第二行：要拦截所有导弹最少要配备的系统数。 【输入样例】 389 207 155 300 299 170 158 65 【输出样例】 6 2

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int a[1001],b[1001],h[1001],n;
//a数组是用来存储导弹高度的，b数组是用来存储最长子序列的，c序列是用来存储发射台高度的 
int main() {
    int i=1,sum=0;
    while(cin>>a[i]){ //输入导弹高度 
        int maxx=0; //暂时存储最大值 
        for(int j=1;j<=i-1;j++){
            if(a[j]>=a[i]){  //如果前面的导弹比现在的高 
            if(b[j]>maxx) maxx=b[j];//要比较前面的最优子序列 
    }
}
    b[i]=maxx+1;
    sum=max(sum,b[i]);
    //这部分是求最多能拦截的导弹数量，及求出最长子序列 
    int l=0;//l是用来存储下标的 
    for(int j=1;j<=n;j++){
        if(h[j]>=a[i]){
            if(l==0) l=j;
            else if(h[j]<h[l]) l=j;
        }
    }
    if(l==0) {
        n++;l=n;
    }
    h[l]=a[i];
    i++;//求的是发射台数量 
}
cout<<sum<<endl<<n<<endl;
      return 0;
}