#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
int n;
long long a[10001] , f[10001] = {0};
int i , j , maxl = 0;
cin >> n;
for (i = 0 ; i < n ; i++)
{
cin >> a[i];
}
f[0] = 1;
for (i = 1 ; i < n ; i++)
{
maxl = 0;
for (j = i - 1 ;j >= 0 ; j--)
{
if (a[j] >= a[i] && f[j] > maxl)
maxl = f[j];
}
f[i] = 1 + maxl;
}
maxl = f[0];
for (i = 1 ; i < n ; i++)
{
if (f[i] > maxl) maxl = f[i];
}
cout << maxl << ' ';
f[0] = 1;
for (i = 1 ; i < n ; i++)
{
maxl = 0;
for (j = i - 1 ;j >= 0 ; j--)
{
if (a[j] <= a[i] && f[j] > maxl)
maxl = f[j];
}
f[i] = 1 + maxl;
}
maxl = f[0];
for (i = 1 ; i < n ; i++)
{
if (f[i] > maxl) maxl = f[i];
}
cout << maxl << endl;
//system("PAUSE");
return EXIT_SUCCESS;
}
答案是：找出该数串的最长不下降
分析：由题意可知，如果拦截了一棵导弹，那么后面的导弹就只能拦截到更低的，也就是说，后面如果有高度更高的导弹就拦截不到了，所以最长不下降子序列已经是最下限了。
必要性：假设拦截系统的数目小于最长子序列长度，可以明显的看到，最长不下降子序列里面的元素都不能被拦截完！
充分性：现在我们把找出的最长不下降子序列的元素从初始数据中移除，在从处理后的数串中找到新的最长不下降子序列，这个新的子序列长度肯定不能大于上次找到的那个序列长度，如果要拦截这个新的序列，那么用上次确定的拦截系统可定绰绰有余。
假设上次找的的最长字串中有两个相邻元素list[p],list[q]，在第二次找到的最长字串中可能存在位于p,q之间的元素记为list[k0],list[k1],……,list[kx](p<=k0,k1,……,kx<=q)，如果list[k0]>list[p]，就将list[k0]与list[q]分到一组，否则就和list[p]分到一组。然后以此类推。
可能你在怀疑这种处理方法的正确性！
现在把第一次找到最长字串最后一个元素记为list[i]，第二次找到的最长字串的最后一个元素记为list[j]，如果list[j]>list[i]，并且j>i (list[j]在list[i]之后出现)，那么把list[i],list[j]不能由一个拦截系统拦截！但是，这种情况不可能出现，如果在list[i]之后还有一个list[j]那么我在第一次确定最长不下降字串的时候，最后一个元素不是list[i]而是list[j]。也就是说在list[i]之后不可能存在比list[i]还大的元素
同理，在第一次找到的最长字串的第一个元素之前不肯能找到更小的元素