Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anton Kuznetsov                      2:5030/566.13  15 Apr 2002  21:59:00
 To : Sergey Politov
 Subject : Интересная задача
 -------------------------------------------------------------------------------- 
 
 
 
 А 15 Апр 02 04:22 Sergey Politov написал Stepan Kuznetsov письмо, и я решил
 вмешаться:
 
  SP> //Привет Stepan, //
  SP>
  SP> До меня дошли слухи, что *14.04.02* *17:06:02* пролетало сообщение
  SP> от Stepan к *Sergey Politov* про *"Re: Интересная задача"*. И я решил
  SP> вмешаться.
  SP>
  SP>
  SP> [...]
  SP>
  SP>>> А последовательность может быть pазpывна, т.е. для ababa и acaca,
  SP>>> ответ какой? aaa или a?
  SK>>      В этом случае ответом будет "а". Hо  твое пpедложение с pазpывной
  SK>> последовательностью интеpесно, но тут возникает дpугой вопpос
  SK>> насколько "pазpывной" она может быть.Пpимеp: пеpвый символ с начала
  SK>> последовательности, остальные в конце. И как опpеделить?
  SP>
  SP>   Вообще говоря есть известная задача. Если два упорядоченных
  SP> мильтимножества надо найти максимальное упорядоченное мультимножетсво,
  SP> которое бы содержалось в двух исходных. Решается динамикой. Эту задачу
  SP> можно решать аналогично - т.е. за O(mn), динамически расчитывать f(i,j) -
  SP> максимальная длина общей подпоследовательноси, заканчивающаяся на i-м и
  SP> j-м символе соответственно, считается ну очень просто.
 
  А может сделать так: f(i) - длина общей подпоследовательности заканчивающаяся
 на i-м символе?
 
                             До свидания, Sergey!
  * Origin: Ya! (2:5030/566.13)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Интересная задача   Stepan Kuznetsov   13 Apr 2002 23:46:59 
 Re: Интересная задача   Sergey Politov   14 Apr 2002 04:50:15 
 Re: Интересная задача   Stepan Kuznetsov   14 Apr 2002 18:06:02 
 Re^2: Интересная задача   Sergey Politov   15 Apr 2002 04:22:40 
 Интересная задача   Anton Kuznetsov   15 Apr 2002 21:59:00 
 Re: Интересная задача   Sergey Politov   17 Apr 2002 04:25:31 
 Re: Интересная задача   Stepan Kuznetsov   17 Apr 2002 23:55:52 
 Интересная задача   Anton Kuznetsov   18 Apr 2002 21:32:00 
 Re^2: Интересная задача   Sergey Politov   18 Apr 2002 04:26:04 
Архивное /ru.algorithms/39343cbb1556.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional