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题