ENG
RUS
Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум
Обсуждение задачи
1143
. Electric Path
Показать все сообщения
Спрятать все сообщения
How to slove it with DP? O(n^3)??
tbtbtb91
4 апр 2004 12:45
Re: How to slove it with DP? O(n^3)??
mkd
5 апр 2004 00:42
It can be solved in O(n^2) time.
Re: How to slove it with DP? O(n^3)??
tbtbtb
5 апр 2004 10:20
How?? Give me some hints?
Re: How to slove it with DP? O(n^3)??
tbtbtb
5 апр 2004 10:58
Is it right??
for s:=n downto 1 do
begin
d[s,1,1]:=0;
d[s,1,0]:=0;
for L:=2 to n+1-s do
begin
d[s,L,0]:=min(dis(s,s+1)+d[s+1,L-1,0],dis(s,s+L-1)+d[s+1,L-1,1]);
d[s,L,1]:=min(dis(s+L-1,s+L-2)+d[s,L-1,1],dis(s+L-1,s)+d[s,L-1,0]);
end;
end;
end;
© 2000–2024
Timus Online Judge Team
. Все права защищены.