分享
 
 
 

防卫导弹(动态规划入门题)

王朝other·作者佚名  2006-06-24
窄屏简体版  字體: |||超大  

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

它是该次测试中第一个被防卫导弹截击的导弹;

它是在上一次被截击导弹的发射后发射,且高度不大于上一次被截击导弹的高度的导弹.

输入格式:

从当前目录下的文本文件"CATCHER.DAT"读入数据.该文件的第一行是一个整数N(0〈=N〈=4000),表示本次测试中,发射的进攻导弹数,以下N行每行各有一个整数hi(0〈=hi〈=32767),表示第i个进攻导弹的高度.文件中各行的行首,行末无多余空格,输入文件中给出的导弹是按发射顺序排列的.

输出格式:

答案输出到当前目录下的文本文件"CATCHER.OUT"中,该文件第一行是一个整数max,表示最多能截击的进攻导弹数,以下的max行每行各有一个整数,表示各个被截击的进攻导弹的编号(按被截击的先后顺序排列).输出的答案可能不唯一,只要输出其中任一解即可.

题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列 ,用一个一维数组Max[ i ]来建立动态规划状态转移方程,表示表示当前状态(从i 到n)最多可击落的导弹数,用next[i]表示当前节点的后继标志:

#include<iostream>

#include<string>

using namespace std;

int h[4001],Max[4001],next[4001];

int main()

{

freopen("in.txt","r",stdin);

freopen("out.txt","w",stdout);

int n,head,i,j,maxnum;

while(cin>>n)

{

for(i=1;i<=n;i++)

cin>>h[i];

maxnum=0;

for(i=n;i>=1;i--)

{

Max[i]=1;

next[i]=0;

for(j=i+1;j<=n;j++)

if(h[i]>=h[j])

if(Max[i]<Max[j]+1)

{

Max[i]=Max[j]+1;

next[i]=j;

}

if(Max[i]>maxnum)

{

maxnum=Max[i];

head=i;

}

}

cout<<maxnum<<endl;

while(head!=0)

{

cout<<head<<endl;

head=next[head];

}

cout<<endl;

}

return 0;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有