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

Обсуждение задачи 1651. Кратчайшая подцепь

tle on 21
Послано daizhenyang 16 фев 2011 22:22
who can help me?
I use bfs.
Re: tle on 21
Послано [NKU]sweet 3 мар 2011 13:10
use dynamic programming
seq:1 2 7 3 2 8 4 8 5
dp :1 2 3 4 2 3 4 3 4
dp[i] -> dp[i+1]
or
dp[i] -> dp[j] while seq[i] == seq[j]
Notice that if much j exists, just goto the smallest j
the algorithm is O(N)

P.S : why netflow doesn't work now ? :)