ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1078. Отрезки

Please help me...WA #1 ;((((((((((((
Послано NoX 16 ноя 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 ;((((((((((((
Послано Bluejack 05-2 Team 17 ноя 2005 08:47
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.