您的位置：程序门 -> c/c++ -> c++ 语言

防导弹问题（c++)

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

防导弹问题（c++)

发表于：2007-07-20 22:40:49 楼主

由用户输入n个数代表n个导弹的高度,输入数的次序代表敌人发射导弹的次序,要求你求出我们的防导弹系统最多能挡住敌人几个导弹.
防导弹系统的规则如下:
第i次防导弹系统所能达到的高度不能小于第j次（i <j),即第一次所达高度最高,往后依次次之.
比如输入:9 8 7 6 5 4 则可以全部拦住输出6
7 8 9 6 3 2 最多能拦住4个7 6 3 2或者8 6 3 2或则9 6 3 2 输出4
5 4 12 10 9 8 13 7 6 相应拦截的高度依次为12 10 9 8 7 6 输出6

发表于：2007-07-21 00:45:511楼得分:0

使用一个循环嵌套就可以了
for（int i=0;i <=n;i++)
{
for（int j=i;j <=n;j++)
{
if（ch[i]> ch[j]) temp++;
}
if（count <temp) count = temp;
temp = 0;
}
运行过了，和你的要求完全一样。

发表于：2007-07-21 01:40:572楼得分:0

很经典的dp题目,建议google "最长上升子序列 "

发表于：2007-07-21 07:01:203楼得分:0

这个是n*logn的一个算法，
http://imlazy.yculblog.com/post.1558727.html

发表于：2007-07-21 10:37:484楼得分:0

呵呵，我是菜鸟，没楼上3位大侠那样的见解，写了个很笨的程序.如下：
//由用户输入n个数代表n个导弹的高度,输入数的次序代表敌人发射导弹的次序,要求你求出我们的防导弹系统最多能挡住敌人几个导弹.
//防导弹系统的规则如下:
//第i次防导弹系统所能达到的高度不能小于第j次（i <j),即第一次所达高度最高,往后依次次之.
//比如输入:9 8 7 6 5 4 则可以全部拦住输出6
//7 8 9 6 3 2 最多能拦住4个7 6 3 2或者8 6 3 2或则9 6 3 2 输出4
//5 4 12 10 9 8 13 7 6 相应拦截的高度依次为12 10 9 8 7 6 输出6
#include <iostream>
using namespace std;
void main（)
{
float *p;int m,h;
cout < < "请输入敌人发射导弹的数目 " < <endl;
cin> > m;
p=new float [m];
for（int i=0;i <m;i++)
{
cout < < "请输入敌人第 " < <i+1 < < "枚导弹的高度 " < <endl;
cin> > p[i];
}
cout < < "敌人导弹的高度分别是： " < <endl;
for（i=0;i <m;i++)
{
cout < <p[i] < < " ";
}
for（int j=0;j <m;j++)
{
h=0;
for（int i=j;i <m;i++)
{
if（p[j]> p[i])
{
h++;
}
}
p[j]=h;
}
for（i=1;i <m;i++)
{

if（p[i-1]> p[i])
{
p[i]=p[i-1];
}
}

cout < < "可以拦截导弹的数量是： " < <p[m-1]+1 < <endl;
cin> > m;//这一行是没有任何作用的，只是让程序在运行的时候停住，让自己看到结果
}

发表于：2007-07-21 10:39:145楼得分:0

对了，上面最后之所以会是p[m-1]+1是因为第一颗导弹中是可以拦截的

发表于：2007-07-21 12:52:526楼得分:0

高中时做过这道题,是noi的练习题,如上面所说,是典型的dp（动态规划)题,可以搜索 "最长不下降序列 "来学习.相关的知识打出来太多.

lz加油~

发表于：2007-07-21 13:28:337楼得分:0

http://www.yuanma.org/data/2007/0509/article_2590.htm

。一句话解决