|
|
back to boardPlease help me...WA #1 ;(((((((((((( Posted by NoX 16 Nov 2005 22:25 I can`t understand why my program has Wrong Answer on test #1... Here is my program: program z1078; {$APPTYPE CONSOLE} uses SysUtils; const maxn=500; type tSeg=record x,y:integer; end; tMyEl=record value:array[1..maxn]of boolean; end; var n,i,j,k:integer; seg:array[1..maxn]of tSeg; m:array[1..maxn,1..maxn]of boolean; flag:boolean; el,maxel:tMyEl; color:array[1..maxn]of boolean; maxcount:integer; l:array[1..maxn]of integer; procedure SIG(v,count:integer;el:tMyEl); var i:integer; begin el.value[v]:=true; color[v]:=true; if count>maxcount then begin maxcount:=count; maxel:=el; end; for i:=1 to n do begin if m[v,i] and not color[i] then SIG(i,count+1,el); end; end; procedure SortThis(n:integer); var min,s,j,imin:integer; begin for s:=1 to n-1 do begin min:=l[s]; imin:=s; for j:=s+1 to n do if (seg[l[j]].y-seg[l[j]].x)<(seg[l[imin]].y-seg[l[imin]].x) then begin imin:=j; min:=l[j]; end; l[imin]:=l[s]; l[s]:=min; end; end; begin readln(n); for i:=1 to n do readln(seg[i].x,seg[i].y); for i:=1 to n do for j:=1 to n do m[i,j]:=false; for i:=1 to n do begin for j:=1 to n do begin if (seg[j].x>seg[i].x) and (seg[j].y<seg[i].y) then m[i,j]:=true; end; end; maxcount:=0; for i:=1 to n do begin for j:=1 to n do el.value[j]:=false; for j:=1 to n do color[j]:=false; SIG(i,1,el); end; writeln(maxcount); j:=0; for i:=1 to n do if maxel.value[i] then begin inc(j); l[j]:=i; end; SortThis(j); for i:=1 to j-1 do write(l[i],' '); writeln(l[j]); readln; end. Please... Help me Re: Please help me...WA #1 ;(((((((((((( I think it is DP problem. I use Longest Decreasing SubSequence(LDS). -First sort the point coordinate by y value(ascending) -Then do LDS normally by x value O(N^2) it's enough to get AC from this problem. |
|
|