防卫导弹 解题报告

描述：

一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：
a)它是该次测试中第一个被防卫导弹截击的导弹；
b)它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。

输入：

多个测例。
每个测例第一行是一个整数n（n不超过100），第二行n个整数表示导弹的高度（数字的顺序即发射的顺序）。
n＝0表示输入结束。

输出：

每个测例在单独的一行内输出截击导弹的最大数目。

输入样例：

5
56100661
0

解题思路：利用动态规划，从后先找到各个数的最大的数目，往前求时利用后面以求的数目，这样就不用重复求了。

代码如下：

#include<iostream>
#include<cstring>
usingnamespacestd;
constintMax(105);
intdata[Max];
intnum[Max];//用来记录每个数能够防卫的导弹
intmain()
{
intn;
while(cin>>n&&n)
{
intsum=0;
for(inti=1;i<=n;i++)
{
num[i]=0;
cin>>data[i];
}
for(i=n;i>0;i--)//从后往前找，先找到后面各个数能防卫的最大的
{
for(intj=i+1;j<=n;j++)
if(data[j]<=data[i])
{
if(num[i]<num[j]+1)
num[i]=num[j]+1;
if(num[i]>sum)
sum=num[i];
}
}
cout<<sum+1<<endl;
}
return0;
}