算法训练 拦截导弹

这道题目来自1999年NOIP全国联赛提高组。是一个基础的序列型动态规划问题。看到题目就知道第一个问题是严格递减子序列问题。比较有趣的是第二个问题，最少需要几套系统才能拦截所有导弹，就是有多少个递减序列。第一个想法就是把最长的递减子序列给排除之后对剩余的元素再来排除，最终得到最后结果。但是这个想法实现比较困难。

这里给出答案，即序列的最长单调递增序列长度为第二问的答案。

假如某序列完全递减，则最长递增子序列长度为1，即只有一个最长递减子序列。
假如某序列完全递增，则最长递增子序列长度为n，即有n个最长递减子序列。（n为该序列长度）
那么对于某序列有增有减，则该序列所形成的严格单调递增序列必然为其每个互相完全不相同单调递减序列的某一个元素共同构成，即对于序列100 68 66 56 78 89 66 20 9，其严格单调递增序列为56 78 89。显然56，78，89永远为三个不同的递减序列中的元素。

假如严格单调递增序列的元素不为不同的递减序列的元素。即某个递减序列贡献了多个元素为严格单调递增序列元素，那么显然这多个元素是单调递增的，与递减序列矛盾。即可证明。

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int i=0,res=0,ans=0;
	int mis[21]={0},up[21]={0},down[21]={0};
	while(cin>>mis[i])
	{
		int _max=0,max_=0;
		up[i]=1;down[i]=1;
		for(int j=0;j<i;j++)
		{
			if(mis[j]<mis[i]&&up[j]>_max)
			 _max=up[j];
			if(mis[j]>mis[i]&&down[j]>max_)
			 max_=down[j];
		}
	up[i]=_max+1;
	down[i]=max_+1;
	res=max(res,up[i]);
	ans=max(ans,down[i]);
	i++;
	}
	cout<<ans<<endl<<res;
	return 0;
 }