求帮忙指出问题!

P1983 [NOIP2013 普及组] 车站分级

huangyizhan @ 2016-04-13 22:30:56

我的想法是:先看出跑过的车站肯定比没跑过的车站等级高(设一趟路径停靠站点为S[I],那么S[1]前面的点不能算上,还有若后面是连着的,说明他有跑了最低等级车站的可能,不能算上),然后再枚举集合的可能情况。

我是这么枚举的:FA【i,J】表示第I躺车次,停靠为J的所属集合,指向最先放入该集合的车站序号

然后枚举各个车站所属集合(i与I-1..1比较,若符合EQUAL函数中的一大堆条件,则把I归入I-1的集合里)。

结果只有10分..求帮忙!

VAR n,m,i,j,k,count:integer; 
    s:array[1..1001,1..1001] of integer;
    FA:ARRAY[1..1001,1..1001] of integer;
    num,ans:array[1..1001] of integer;
    flag:array[1..1001] of boolean;
function equal(a,b:integer):boolean;
var p:integer;
begin  
  for p:=1 to m do
  begin
     if (a<s[p,1]) and (b<s[p,1]) then continue;
     if (a<=s[p,num[p]]) and (b<=s[p,num[p]]) and 
         (a>=s[p,1]) and (b>=s[p,1]) and (fa[p,b]=fa[p,a]) then continue;
     if (a>=s[p,1]) and (a<=s[p,num[p]])  and (b<s[p,1]) then continue;
     if (a>s[p,num[p]]) and (b>s[p,num[p]]) then continue;
     if (b>=s[p,1]) and (b<=s[p,num[p]]) and (a>s[p,num[p]]) and ( fa[p,b]=fa[p,a]) then continue;
     if (fa[p,a]=-1) or (fa[p,b]=-1) then continue;
  exit(false);
  end;
  equal:=true;
end;
procedure dealspecial(x:integer);
var q:integer;
begin
 if s[x,num[x]]=n then 
 begin
  fa[x,n]:=-1;
  q:=0;
  for q:=num[x] downto 2 do 
   begin
    if s[x,q]=s[x,q-1]+1 then fa[x,s[x,q-1]]:=-1 else  break; 
   end;
end;
end;
begin
 fillchar(flag,sizeof(flag),false);
 fillchar(fa,sizeof(fa),0);
 count:=0;
  read(n,m);
   for i:=1 to m do 
   begin
     read(num[i]);
     for j:=1 to num[i] do read(s[i,j]);
   end;
   for i:=1 to m do
  begin
     for j:=1 to num[i] do
       fa[i,s[i,j]]:=s[i,1];//初始化集合
      dealspecial(i);//fa[I,j]表示第I躺车,中的站号(与S[I,J]的J不同)J的集合指向
   end;
  { for i:=1 to m do 
    begin for j:=1 to num[i] do 
    write(s[i,j]);
    writeln;
    end;}
    for I:=1 TO N do
    begin
    ans[i]:=i;
      for j:=1 to i-1 do
      begin
      if equal(i,j) then begin ans[i]:=ans[j]; break; end;//把I并进J的集合
      end;
   if not flag[ans[i]] then begin flag[ans[i]]:=true;inc(count); end;
    end;
    //for i:=1 to n do write(ans[i],' ');
    write(count);
end.

by huangyizhan @ 2016-04-13 22:48:57

2013PJ第4题


|