首页 > 代码库 > 刷题总结——拦截导弹(ssoj)

刷题总结——拦截导弹(ssoj)

题目:

题目背景

NOIP1999 提高组试题

题目描述

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

输入格式

只有一行,为空格隔开的n(1<=n<=1000)个正整数序列。

输出格式

第一行是一个正整数,为最多能拦截的导弹数量。
第二行是一个正整数,为拦截所有导弹需要配备拦截系统的套数。

样例数据 1

输入  [复制]

 

 

389 207 155 300 299 170 158 65

输出


2

题解:

  第一个问很简单就是将数组反过来后求最长不下降序列的长度;

  第二个问用一个定理:一个数列中最少的不下降序列的个数等于该数列的最长上升(注意不是最长不下降序列)的长度!!

代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=2000;
int num[N],n=0,ans=0,maxx=0,dp[N];
int main()
{
 // freopen("a.in","r",stdin);
  while(scanf("%d",&num[++n])!=EOF);
  n--;
  for(int i=1;i<=n;i++) 
  {
    int left=1,right=maxx;
    while(left<=right)
    {
      int mid=(right+left)/2;
      if(num[i]<dp[mid])
        right=mid-1;
      else
        left=mid+1;
    }
    if(left>maxx)  maxx++;
    dp[left]=num[i];
  }
  reverse(num+1,num+n+1);
  memset(dp,0,sizeof(dp));
  for(int i=1;i<=n;i++) 
  {
    int left=1,right=ans;
    while(left<=right)
    {
      int mid=(right+left)/2;
      if(num[i]<=dp[mid])
        right=mid-1;
      else
        left=mid+1;
    }
    if(left>ans)  ans++;
    dp[left]=num[i];
  }
  cout<<ans<<endl;
  cout<<maxx<<endl;
  return 0;
}
 

 

刷题总结——拦截导弹(ssoj)