Сервер олимпиад

Ставропольский государственный университет

Имя
Пароль

Server Off-Line
Server time: 05 Oct 2024 06:27:08

Форум

Задача Строки из Турнир Stavsu RCI 2007 - март
Автор Сообщение
Zakhr
Новичок

Зарегистрирован: 24.08.2006
Сообщения: 12

Добавлено: 09.04.2007 17:42:25
Как её решать?
Я её пытался решить так динамикой составлял таблицу всех подстрок потом проходил по таблице и рассматривал каждый вариант проверял на полуторность строки и находил наибольшую такую подстроку.
Но получил неверный ответ.
Zakhr
Новичок

Зарегистрирован: 24.08.2006
Сообщения: 12

Добавлено: 09.04.2007 17:43:22
Как её решать?
Я её пытался решить так динамикой составлял таблицу всех подстрок потом проходил по таблице и рассматривал каждый вариант проверял на полуторность строки и находил наибольшую такую подстроку.
Но получил неверный ответ.
ilia_night
Новичок

Зарегистрирован: 27.02.2007
Сообщения: 16

Добавлено: 09.04.2007 18:25:32
У меня есть несколько вариантов , почему оно у тебя не работет:
1)А не забыл ли ты удалить одинаковые символы?
2)Зачем проверять на полуторность, если надо было просто взять и поместить чётные символы одной строки в первый массив нечётные во второй, и аналогично со второй строкой.
3)Зайди на wikiпедию , и поищи раздел lcs , там написан классический алгоритм с динамикой.
admin
Администратор

Зарегистрирован: 09.03.2006
Сообщения: 132

Добавлено: 10.04.2007 13:25:28
решение разбивается на 4 подрешения, удовлетворяющие условию.
А далее - стандартный алгоритм поиска подпоследовательности максимальной длины через динамику.
(квадратная матрица и т.д.). - стандартный пример на подстроках.
Zakhr
Новичок

Зарегистрирован: 24.08.2006
Сообщения: 12

Добавлено: 11.04.2007 21:23:59
Thanks
Страницы: [ 1 ]
Rambler's Top100 | Карта сайта | Контакты | Copyright © 2005-2007, Ставропольский государственный университет.