: .
动态规划初步
LT
个元素为最后一个元素时的最长不上升序列的长度len(i),递推公式为len(1)=1,len(i)=max(len(j)+1),其中i>1,j=1,2,…i-1,且j同时要满足条件:序列中第j个元素大于等于第i个元素。
第二部分比较有意思。由于它紧接着第一问,所以很容易受前面的影响,采取多次求最长不上升序列的办法,然后得出总次数,其实这是不对的。要举反例并不难,比如长为7的高度序列“7 5 4 1 6 3 2”, 最长不上升序列为“7 5 4 3 2”,用多次求最长不上升序列的结果为3套系统;但其实只要2套,分别击落“7 5 4 1”与“6 3 2”。那么,正确的做法又是什么呢?
我们的目标是用最少的系统击落所有导弹,至于系统之间怎么分配导弹数目则无关紧要;上面错误的想法正是承袭了“一套系统尽量多拦截导弹”的思维定势,忽视了最优解中各个系统拦截数较为平均的情况,本质上是一种贪心算法。如果从每套系统拦截的导弹方面来想行不通的话,我们就应该换一个思路,从拦截某个导弹所选的系统入手。
题目告诉我们,已有系统目前的瞄准高度必须不低于来犯导弹高度,所以,当已有的系统均无法拦截该导弹时,就不得不启用新系统。如果已有系统中有一个能拦截该导弹,我们是应该继续使用它,还是另起炉灶呢?事实是:无论用哪套系统,只要拦截了这枚导弹,那么系统的瞄准高度就等于导弹高度,这一点对旧的或新的系统都适用。而新系统能拦截的导弹高度最高,即新系统的性能优于任意一套已使用的系统。既然如此,我们当然应该选择已有的系统。如果已有系统中有多个可以拦截该导弹,究竟选哪一个呢?当前瞄准高度较高的系统的“潜力”较大,而瞄准高度较低的系统则不同,它能打下的导弹别的系统也能打下,它够不到的导弹却未必是别的系统所够不到的。所以,当有多个系统供选择时,要选瞄准高度最低的使用,当然瞄准高度同时也要大于等于来犯导弹高度。
解题时,用一个数组记下已有系统的当前瞄准高度,数据个数就是系统数目。
[程序清单]
const max=1000;
var i,j,current,maxlong,minheight,select,tail,total:longint;
height,longest,sys:array [1..max] of longint;
line:string;
begin
write('Input test data:');
readln(line);
i:=1;
while i<=length(line) do
begin
while (i<=length(line)) and (line[i]=' ') do i:=i+1;
current:=0;
while (i<=length(line)) and (line[i]<>' ') do
begin
current:=current*10+ord(line[i])-ord('0');
i:=i+1
end;
total:=total+1;
height[total]:=current
end;
longest[1]:=1;
for i:=2 to total do
begin
maxlong:=1;
for j:=1 to i-1 do
begin
if height[i]<=height[j]
then if longest[j]+1>maxlong
then maxlong:=longest[j]+1;
longest[i]:=maxlong
end;
end;
maxlong:=longest[1];
for i:=2 to total do
if longest[i]>maxlong then maxlong:=long
动态规划初步 来自淘豆网www.taodocs.com转载请标明出处.