动态规划之最长非升降子序列

《动态规划之最长非升降子序列》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划之最长非升/降子序列一、最长非升/降子序列1、导弹拦截(vijosPl303)【描述】某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统,因此有可能不能拦截所有的导弹。【输入格式】输入数据只有一行，该行包含若干个数据，Z间用半角逗号隔开，表示导弹依次飞来的高度(导弹最多有20枚，其高度为不大于30000的正整数)。【输出格式】输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第

2、一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。[算法分析]本题的问题1本质是在一个数列中寻求递减的、未必连续的最长子序列。问题2：若导弹i的高度高于所有系统的最低高度(最后一个导弹的高度)，则断定导弹i不能被这些系统所拦截，应增设一套系统來拦截导弹i,所以用一个数组记录各系统的最低高度。若导弹i低于某些系统的最低高度，那么导弹i均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数最少，不妨采用贪心策略，选择其中最低高度最小的一套系统(问题2实质上也是一个求最长上升子序列)h[i,l]:数列(导弹高度)h「i,2]

3、:导弹i…导弹n中可被拦截的最多导弹数。sys[k]:到目前为止被第k套系统拦截的导弹中，最后一枚导弹的高度。programp!303;varn,m:integer;h:array[1..20,1..2]ofinteger;sys:arrayfl..20]ofinteger;procedureinit;vari,j,l,k,c:integer;substring;beginfillchar(h,sizeof(h),0);assign(input,'d1303.txt');reset(input);readln(s);close(input);n:=0;repeatk:=po

4、s('；,s);ifk>0thens1:=copy(s,l,k-l)elsesl:=s;inc(n);val(sl,h[n,l],c);ifk>0thendelete(sj.k);untilk=0;end;procedurework;varij,max,ml,min,mi:integer;beginh[n,2]:=l;ml:=l;fori:=n-ldownto1dobeginmax:=0;forj:=i+ltondoif(h[j,l]max)thenmax:=hfj,2];h[i,2]:=max+l;ifmax+l>mlthenml:=

5、max+l;end;m:=0;fori:=ltondobeginmin:=maxint;forj:=ltomdoif(sys[j]>h[i,l])and(sys[j]

6、的鹰比自己飞行的有技巧。于是，他们决定举办一场比赛，比赛的地方将在一个迷宫之中。这些鹰的起始点被设在一个N*M矩阵的左下角map[l,1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角，有些map[i,j]是可以从中I'可穿越的。每一个方格的边长都是100米。如图所示：没有障碍，也没有死路。这样设计主要是为了高速飞行的鹰们不要发现死路来不及调整而发生意外。潘帕斯雄鹰冒着减RP的危险从比赛承办方戒备森严的基地中偷来了施工的地图。但是问题也随之而来，他必须在比赛开始之前把地图的每一条路都搞清楚，从中找到一-条到达终点最近的路。(哈哈，笨鸟不先飞也要拿冠军)但是此鹰是

7、前无古鹰，后无來鹰的吃菜长大的鹰■■菜鸟。他自己没有办法得出最短的路径，于是紧急之下找到了学OI的你，希望找到你的帮助。【输入格式】首行为n,m(On,m的最短路径的长度，四舍五入保留到整数即可样例输入323113212样例输出383【算法分析】若没有特殊边，则路径长度为m+n(每个格子边t为1),每一个特殊边可使路径长度减少2-sqrt(2)