算法效率绝对是最烂的(大鸟无喷)，时间空间效率完全没有考虑，但是可能是最直观的，最白痴的思路。没有运用XXX算法思想，就是保证没读过算法相关书籍的任何人都能读懂。
题目出处：http://www.programfan.com/acm/show.asp?qid=5

题目如下：
防御导弹
Problem
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
Input
最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数）
Output
两个整数M和N。表示：这套系统最多能拦截 M 枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。
Sample Input
300 250 275 252 200 138 245
Sample Output
5 2

首先，最直观的思考如下：
问题翻译：本问题就是要求解某个随机序列的最长降序序列
思考：
对于目标序列S，分成两段，其中S1为已经遍历过的，S2为未遍历过的。
运用某种数据结构，存储S1中所有可能的降序序列段，然后每次把S2中的第一个元素加入S1，并修改S1所有的降序序列段，保证新生成的降序序列段为新的S1的降序序列段。
通过这个思路，可以想到用AOV网（拓扑排序）来存储所有的降序序列段，每次从S2获得新的元素添加进S1就相当于遍历树的所有节点，如果已存储的节点的值大于等于新节点的值，则把该新节点的副本加入该节点的子序列。

所求的最长序列M就是AOV网的深度，所求的需要多少个系统N就是AOV网的终端节点数量。

源码：

//代码分析：为了保证代码的通用性（不仅仅局限于int类型），使用泛型编程。
//			为了保证内存管理的方便性，使用智能指针。

#include <vector>
#include <memory>
#include <algorithm>
#include <iostream>

#define MAXALTITUDE 30000						//导弹最高高度
#define GETARRAYSIZE(A) (sizeof(A)/sizeof(*A))	//得到数组中元素的个数

static int count = 0;//核心语句计数量

template<class T>
class DescendAov
{
private:
	bool isVisit;											//是否访问过
	T value;												//存储当前节点的值
	std::vector<std::shared_ptr<DescendAov> > minSet;		//存储比该节点值小的集合
	void TerminalCount(int &num)
	{//终端节点计数
		if (isVisit)
			return;
		isVisit = true;
		if (minSet.empty())
			++num;
		for (auto itr : minSet)
			itr->TerminalCount(num);
	}
	void Insert(const std::shared_ptr<DescendAov> d)
	{//插入后继
		++count;
		if (d->value <= value && this != d.get())
		{//如果节点值value大于等于新加入的节点值d->value，则添加进比他小的集合，this!=d.get()是为了防止自身重复插入自身。
			for (auto itr : minSet)
				itr->Insert(d);
			minSet.push_back(d);
		}
	}
	void Insert(const T &t)
	{
		Insert(std::shared_ptr<DescendAov<T>>(new DescendAov<T>(t)));
	}
public:
	DescendAov(const T v) :value(v),isVisit(false){};//通过值建AOV网
	DescendAov(T* sequence, int length) :DescendAov(MAXALTITUDE)
	{//通过序列建AOV网
		for (int i = 0; i < length; ++i)
		{//创建目标数据结构
			Insert(sequence[i]);
		}
	};
	int GetTheLengthOfTheLongestDescendSequence(int i = 0)
	{//遍历AOV网，得到AOV网的高度，就是所要求的最大降序序列长度
		int high = i;
		for (auto itr : minSet)
			high = std::max(itr->GetTheLengthOfTheLongestDescendSequence(i + 1), high);
		return high;
	}
	int GetTheTerminalNumber()
	{//统计终端节点数量
		int num = 0;
		TerminalCount(num);
		return num;
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	int missile[] = {300,250,275,252,200,138,245};//元素个数不要超过7，不然会出现很恐怖的事，接下来给出解释，为什么很恐怖
	DescendAov<int> root(missile, GETARRAYSIZE(missile));
	std::cout << "最多拦截的导弹数：" << root.GetTheLengthOfTheLongestDescendSequence() << std::endl;
	std::cout << "需要多少套系统：" << root.GetTheTerminalNumber() << std::endl;
	std::cout << "核心代码循环次数:" << count << std::endl;
	return 0;
}

问题分析：

这种算法有个致命的问题：
为什么数组元素不能超过7？我们可以假设数组元素个数为n，那么树的展开速度将是n*n*n.....n，也就是n^n方。7的7次方是823543，到8^8时将是一个天文数字。

防御导弹算法