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

Обсуждение задачи 1861. Кладбище в Дейе

Some hints needed.
Послано 72VanVector[SevNTU] 24 сен 2011 22:19
Can somebody give hints to solve this task?
Re: Some hints needed.
Послано svr 8 окт 2011 19:06
Conflict graph may help.
Positions of possible substrings are vertices and two positions
conflict if they  can not be  simultaneously.
Answer= max number of independent vertices.
Also let relation a<b means that position is before of  position b and they don't conflict.Then a<b,b<c=> a<c so we have an order. Answer is a height of ordered structure.

Edited by author 08.10.2011 19:07
Re: Some hints needed.
Послано bsu.mmf.team 9 окт 2011 02:04
Just easy DP.
Re: Some hints needed.
Послано svr 10 окт 2011 11:47
But Dp may be difficult- problem of 35 test.
When poset is used and standard dfs for it's height we have Ac without any problems.