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

Обсуждение задачи 1112. Покрытие

WA on test 1,it is terrible!
Послано bbs.hasea.com 18 сен 2007 20:48
#include <iostream>

using namespace std;

int main ()
{
    long n;
    long i,j,k,p;
    long zz,maxn,nowmax,wz;
    long l[100],r[100];
    long xout[100],yout[100];
    long much[100];
    long shangyige[100];

    for (i=0;i<100;i++)
        {
        l[i]=0;
        r[i]=0;
        much[i]=0;
        xout[i]=0;
        yout[i]=0;
        shangyige[i]=0;
        }
    cin>>n;
    for (i=1;i<=n;i++)
        {
        cin>>l[i]>>r[i];
        if (l[i]>r[i]) {
                       zz=l[i];
                       l[i]=r[i];
                       r[i]=zz;
                       }
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (l[i]>l[j]) {
                           zz=l[i];
                           l[i]=l[j];
                           l[j]=zz;
                           zz=r[i];
                           r[i]=r[j];
                           r[j]=zz;
                           }
    maxn=0;
    much[1]=1;
    shangyige[1]=0;
    for (i=2;i<=n;i++)
        {
        nowmax=0;
        for (j=1;j<i;j++)
            {
            p=1;
            k=j;
            while (k!=0)
                  {
                  if ((l[k]<r[i])&&(r[k]>r[i])) {
                                                p=0;
                                                break;
                                                }
                  k=shangyige[k];
                  }
            if (p==1) {
                      if (much[j]>nowmax) {
                                          nowmax=much[j];
                                          wz=j;
                                          }
                      }
            }
        if (nowmax==0) {
                       much[i]=1;
                       shangyige[i]=0;
                       }
                       else {
                            much[i]=nowmax+1;
                            shangyige[i]=wz;
                            }
        }
    nowmax=0;
    for (i=1;i<=n;i++)
        if (much[i]>nowmax) {
                            nowmax=much[i];
                            wz=i;
                            }
    cout<<nowmax<<endl;
    i=wz;
    j=1;
    while (i!=0)
          {
          xout[j]=l[i];
          yout[j]=r[i];
          j++;
          i=shangyige[i];
          }
    for (i=1;i<j;i++)
        cout<<xout[i]<<" "<<yout[i]<<endl;
    return (0);
}