作业帮NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/30 17:24:07
NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明
NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明
NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明
第二问朴素的是“潜力法”.就是用打的最低的炮台去打这个导弹.
更好的算法是求出所有下降序列的个数,即求最长上升序列.因为dilworth定理.
dilworth定理：最长的上升子序列每一个成员必不属于同一个下降子序列.
证明：设最长不降子序列中元素 ai,aj (i
最多能拦截的导弹数就是求输入序列的最长不升序列长度，总共需要的拦截系统是输入序列的最长上升序列长度，所求即为这个长度减一。
这里要注意的是对输入的处理问题，因为输入序列是用逗号隔开的，不能直接READ，只能作为字符读入后再进行处理，这里有两个可行的办法，一种是一个一个字符读入，遇到逗号就开始存数，另一种是一次性读入整个字符串，再利用pos,copy,delete等字符串处理函数把数...
全部展开
最多能拦截的导弹数就是求输入序列的最长不升序列长度，总共需要的拦截系统是输入序列的最长上升序列长度，所求即为这个长度减一。
这里要注意的是对输入的处理问题，因为输入序列是用逗号隔开的，不能直接READ，只能作为字符读入后再进行处理，这里有两个可行的办法，一种是一个一个字符读入，遇到逗号就开始存数，另一种是一次性读入整个字符串，再利用pos,copy,delete等字符串处理函数把数字提取出来。
程序大概是这样的：
program p8_3(input,output);
const maxn=5000;maxlongint=5001;
var i,j,n,l,maxlen:longint;
a,len,t:array[0..maxn] of longint;
begin
assign(input,'daodan.in');
reset(input);
assign(output,'daodan.out');
rewrite(output);
{这里应该要判断n的值是多少，但我不知道怎么根据输入的数字判断出到底输入了几个数字}
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do len[i]:=1;
for i:=n-1 downto 1 do
for j:=i+1 to n do
if (a[j]
maxlen:=1;
for i:=1 to n do if len[i]>maxlen then maxlen:=len[i];
a[0]:=maxlongint;len[0]:=maxlen+1;
for i:=0 to n do if len[i]=1 then t[i]:=1 else t[i]:=0;
for l:=1 to maxlen do
begin
for i:=n downto 1 do
if len[i]=1 then
begin
j:=i-1;
while (j>=0) and(a[j]<>a[i]) do
begin
if (a[j]>a[i]) and(len[j]=l+1) then inc(t[j],t[i]);
dec(j)
end;
end;
end;
writeln(maxlen,' ',t[0]);
{在网页上要求输出的其实是a[0]-1的值，但老师提供的历年noip试题中a[0]不用减1}
close(input);
close(output);
end.
收起