文档介绍：本题第一问实际上是给出数列a1..an,求最长非递增序列的长度,{容易想到以n来划分子问题,即分别求a1..an-1, a1..an-2, …, a1,中最长非递增序列长度,但各级子问题之间不易建立转化关系}将子问题具体一些,我们可以用f[k]表示数列a1..ak中以ak结尾的最长非递增序列的长度,题目所求即为max{f[1..n]}。转移方程为f[n]=max{f[k]}+1;(0<=k<n,a[n]<=a[k] ) 设a[0]= -maxint,f[0]=0;
第二问可以用贪心做,设拦截前k个导弹用o2个系统,其最后拦截的高度分别为l[1]..l[o2],则拦截第k+1个导弹时,找能够拦截这枚导弹的系统中最后拦截高度最小的,若没有这样的系统则新增一个系统。
附源程序:
const max = 10000;
type arr = array[0..max]of integer;
var d,l : arr;
i,j,k,m,n,o1,o2,t : longint;
procedure input;
begin
fillchar(d,sizeof(d),0);
fillchar(l,sizeof(l),0);
writeln('input:');
i:=0;
repeat
i:=i+1;
read(d[i]);
until eoln;
t:=i;
o1:=0; o2:=0;
end;
procedure output;
begin
writeln('Output:');
writeln(o1);
writeln(o2);
end;
procedure main1;
begin
l[t]:=1;
for i:=t-1 downto 1 do begin
k:=0;
for j:=i+1 to t do
if (l[j]>k)and(d[i]>=d[j]) then k:=l[j];
l[i]:=k+1;
end;
for i:=1 to t do
if l[i]>o1 then o1:=l[i];
end;
procedure main2;
begin
for i:=0 to t do l[i]:=maxint;
o2:=1;
for i:=1 to t do begin
k:=0;
for j:=1 to o2 do
if (l[j]>=d[i])and(l[j]<=l[k]) then k:=j;
if k=0 then begin
o2:=o2+1;
k:=o2;
end;
l[k]:=d[i];
end;
end;
begin
input;
main1;
main2;
output;
end.
第二题石子合并
设f[i,j](i<=j)表示将第i堆到第j堆石子合并为一堆所得的最大分数(最小时类似)。问题所求即为f[1,n]。根据合并规则,f[i,j]的解只于f[i,k],f[k+1,j](i<=k<j)的解有关,即问题的最优解包含了子问题的最优解,具备最优子结构。转移方程为f[i,j]={f[i,k]+f[k+1,j]}+d[p];初始时f[k,k]=0(1<=k<=n);
附源程序:
Program gether_stone;
type
Trock_best = Array[1..100,1..100] of longint;
Trock_k = Array[1..100,1..100] of byte;
Tstone = Array[0..100] of word;
Tbak = Array[1..100] of boolean;
var
rock_best:^Trock_best;
rock_k:Trock_k;
stone,tot:Tstone;
stone1:Tstone;
bak:Tbak;
n:Word;
function count(first,k,last:Word):longint;
var
s1:longint;
begin
if first<=last
then s1:=tot[last]-tot[first-1]
else s1:=tot[n]+tot[last]-tot[first-1];
count:=rock_best^[first,k]+rock_best^[(k mod n)+1,last]+s1;
end;
function try(now,old:longint;job:byte):b