刷题总结——拦截导弹（ssoj）

题目：

题目背景

NOIP1999 提高组试题

题目描述

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

输入格式

只有一行，为空格隔开的n（1<=n<=1000）个正整数序列。

输出格式

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

样例数据 1

输入　 []

 

输出

题解：

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

第二个问用一个定理：一个数列中最少的不上升序列的个数等于该数列的最长上升（注意不是最长不下降序列）的长度！！

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N=;

int num[N],n=,ans=,maxx=,dp[N];

int main()

{

  //freopen("a.in","r",stdin);

  while(scanf("%d",&num[++n])!=EOF);

  n--;

  for(int i=;i<=n;i++)

  {

    int left=,right=maxx;

    while(left<=right)

    {

      int mid=(right+left)/;

      if(num[i]<=dp[mid])

        right=mid-;

      else

        left=mid+;

    }

    if(left>maxx)  maxx++;

    dp[left]=num[i];

  }

  reverse(num+,num+n+);

  memset(dp,,sizeof(dp));

  for(int i=;i<=n;i++)

  {

    int left=,right=ans;

    while(left<=right)

    {

      int mid=(right+left)/;

      if(num[i]<dp[mid])

        right=mid-;

      else

        left=mid+;

    }

    if(left>ans)  ans++;

    dp[left]=num[i];

  }

  cout<<ans<<endl;

  cout<<maxx<<endl;

  return ;

}