回 帖 发 新 帖 刷新版面

主题:TJU1004怎么会超时

经典的防御导弹,我编的超时了,谁帮帮我啊
var
  s,a,prt,s1:array[1..20]of integer;
  i,j,k,l,n,max,n1,sum:integer;
  flag:boolean;
begin
  n:=0;flag:=true;sum:=0;
  while not eoln do
    begin
      read(s[n+1]);
      a[n+1]:=1;
      prt[n+1]:=0;
      inc(n);
    end;
  while true do
    begin
      for i:=2 to n do
        begin
          max:=0;
          for j:=1 to i-1 do
            if (s[j]>=s[i])and(a[j]>max) then begin max:=a[j]; k:=j; end;
          a[i]:=max+1;
          prt[i]:=k;
        end;
      max:=0;inc(sum);
      for i:=1 to n do if a[i]>max then begin max:=a[i]; l:=i; end;
      if flag then write(max,' ');
      while prt[l]<>0 do
        begin
          s[l]:=-1;
          l:=prt[l];
        end;
      s[l]:=-1;
      flag:=false;n1:=0;
      for i:=1 to n do
        if s[i]<>-1 then begin s1[n1+1]:=s[i]; inc(n1); end;
      if n1=0 then break;
      s:=s1;n:=n1;
    end;
  writeln(sum);
end.

回复列表 (共2个回复)

沙发

题目是什么?能具体说说吗?

板凳


var
k,e,j,l,x:byte;
a:array[1..20,1..3]of integer;
begin
while not seekeoln do
begin
inc(k);
read(a[k,1]);
end;
e:=0;j:=0;l:=0;x:=0;
a[k,2]:=1;a[k,3]:=0;
for e:=k-1 downto 1 do
 begin
 l:=0;
 for j:=e+1 to k do
 begin
  if (a[e,1]>=a[j,1]) and (1+a[j,2]>l)
  then begin a[e,3]:=j;a[e,2]:=a[j,2]+1;l:=a[e,2];end;
  if l=0 then a[e,2]:=1;
  end;

end;
for k:=1 to k do
if a[k,2]>x
then x:=a[k,2];
write(x,' ');

e:=0;j:=0;l:=0;x:=0;
a[k,2]:=1;a[k,3]:=0;
for e:=k-1 downto 1 do
 begin
 l:=0;
 for j:=e+1 to k do
 begin
  if (a[e,1]<a[j,1]) and (1+a[j,2]>l)
  then begin a[e,3]:=j;a[e,2]:=a[j,2]+1;l:=a[e,2];end;
  if l=0 then a[e,2]:=1;
  end;

end;
for k:=1 to k do
if a[k,2]>x
then x:=a[k,2];
writeln(x);
end.


我的AC程序。。。。。。

解释一下。。。。第一问相当于求最大不上升子序列。。。。。第二问相当于求最大上升子序列

DP的基础题

当然。 。。。。据说用贪心也可以

我来回复

您尚未登录,请登录后再回复。点此登录或注册