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

Обсуждение задачи 1181. Разрезание окрашенного многоугольника

DP for O(n^3)
Послано [Ural SU] GetTester 6 ноя 2009 14:02
I got AC with O(n^3) solution, based on DP.
I suppose, that testcases are too weak. Anyway, I think, that it's not normal to get AC for O(n^3) solution.
)
Re: DP for O(n^3)
Послано tiancaihb 7 ноя 2009 04:15
My solution is n3, but it doesn't have to check all posibilities. Some part of array f[][] is never used. Besides, I don't know a better way.
Re: DP for O(n^3)
Послано ASK 17 мар 2010 21:32
It is not O(n^3): the expected number of tests for each sub-interval is 2 and thus DP is O(n^2).