//这个我就是来水一发的……算法复杂度 O(n^2)，以后可能会写一下 O(nlogn) 的

题目

传送门=￣ω￣=

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式：

一行，若干个正整数最多 100 个。

输出格式：

2 行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入样例 #1：

389 207 155 300 299 170 158 65

输出样例 #1：

6
2

题解

没别的说的，最长不降子序列解决第一问。

至于第二问，你可能需要知道这个东西：

Dilworth 定理：对于一个偏序集，最少链划分等于最长反链长度。
Dilworth 定理的对偶定理：对于一个偏序集，其最少反链划分数等于其最长链的长度。

也就是说把一个数列划分成最少的最长不升子序列的数目就等于这个数列的最长上升子序列的长度。

至于证明去问度娘，我不会。

代码：

#include <bits/stdc++.h>
using namespace std;
int n=1,h[105],f[105],ans;
int main()
{
    while(cin>>h[n])n++;n--;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)if(h[j]>h[i]&&f[j]+1>f[i])f[i]=f[j]+1;
        ans=max(f[i],ans);
    }
    cout<<ans<<endl;
    ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)if(h[j]<h[i]&&f[j]+1>f[i])f[i]=f[j]+1;
        ans=max(f[i],ans);
    }
    cout<<ans;
    return 0;
}