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

动态规划之最长非升/降子序列 一、最长非升/降子序列 1、导弹拦截（vijos P1303) 【描述】 某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 【输入格式 】 输入数据只有一行，该行包含若干个数据，之间用半角逗号隔开，表示导弹依次飞来的高度（导弹最多有 20 枚，其高度为不大于 30000 的正整数）。 【输出格式】 输出数据只有一行，该行包含两个数据，之间用半角逗号隔开。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。 [算法分析] 本题的问题1本质是在一个数列中寻求递减的、未必连续的最长子序列。 问题2：若导弹i的高度高于所有系统的最低高度（最后一个导弹的高度），则断定导弹i不能被这些系统所拦截，应增设一套系统来拦截导弹i，所以用一个数组记录各系统的最低高度。 若导弹i低于某些系统的最低高度，那么导弹i均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数最少，不妨采用贪心策略，选择其中最低高度最小的一套系统（问题2实质上也是一个求最长上升子序列） h[i,1]:数列（导弹高度） h[i,2]:导弹i…导弹n中可被拦截的最多导弹数。 sys[k]:到目前为止被第k套系统拦截的导弹中，最后一枚导弹的高度。 program p1303; var n,m:integer; h:array[1..20,1..2] of integer; sys:array[1..20] of integer; procedure init; var i,j,l,k,c:integer; s,s1:string; begin fillchar(h,sizeof(h),0); assign(input,d1303.txt); reset(input); readln(s); close(input); n:=0; repeat k:=pos(,,s); if k0 then s1:=copy(s,1,k-1) else s1:=s; inc(n); val(s1,h[n,1],c); if k0 then delete(s,1,k); until k=0; end; procedure work; var i,j,max,ml,min,mi:integer; begin h[n,2]:=1;ml:=1; for i:=n-1 downto 1 do begin max:=0; for j:=i+1 to n do if (h[j,1]h[i,1]) and (h[j,2]max) then max:=h[j,2]; h[i,2]:=max+1; if max+1ml then ml:=max+1; end; m:=0; for i:=1 to n do begin min:=maxint; for j:=1 to m do if (sys[j]h[i,1]) and (sys[j]min) then begin min:=sys[j];mi:=j end; if min=maxint then begin inc(m);sys[m]:=h[i,1] end else begin sys[mi]:=h[i,1] end; end; writeln(ml,,,m-1); end; begin init; work; end. 2.飞翔（vijos P1336） 【描述】 鹰最骄傲的就是翱翔，但是鹰们互相都很嫉妒别的鹰比自己飞的快，更嫉妒其他的鹰比自己飞行的有技巧。于是，他们决定举办一场比赛，比赛的地方将在一个迷宫之中。 这些鹰的起始点被设在一个N*M矩阵的左下角map[1，1]的左下角。终点被设定在矩阵的右上角map[N,M]的右上角，有些map[i,j]是可以从中间穿越的。每一个方格的边长都是100米。如图所示： 没有障碍，也没有死路。这