• Зарегистрирован: 2010-10-04
  • Сообщений: 2

Тема: Конеладьи (задача с КИТ-2009).

Кто-нибудь может подробно объяснить идею решения pls этой задачи:
http://online.contester.ru/ru/problem-p … &smt=6

Как я понял, тут ДП по профилю или что-то подобное. Также где можно почитать про подобные задачи? Спасибо...

2 Ответ от Mishail

  • Mishail
  • Участник
  • Неактивен
  • Откуда: Душанбе, Таджикистан
  • Зарегистрирован: 2010-02-15
  • Сообщений: 19

Re: Конеладьи (задача с КИТ-2009).

Ну эту задачу можно решить так называемым "backtrecking"-ом. Ставим первого конеладью на все возможные места, при этом для каждого возможного места (для первой фигуры) перебираем все возможные места на которых может стоять вторая фигура (с учётом того, что первую мы никуда не убираем), а для всех положения второго перебираем возможные места для третьего и т.д.
В-общем сложно объяснить. Лучше почитай где-нибудь про этот метод (backtracking или метод перебора с отходом назад).
Если хочешь могу написать код решения.

Misha Panyavin [PML]
  • Зарегистрирован: 2010-10-04
  • Сообщений: 2

Re: Конеладьи (задача с КИТ-2009).

Бэктрекинг здесь по времени вряд ли пройдет. Насколько я помню она как-то решается с помощью ДП по профилю, только какого-то необычного.

4 Ответ от cmd

  • cmd
  • Участник
  • Неактивен
  • Откуда: Волжский
  • Зарегистрирован: 2009-06-11
  • Сообщений: 35

Re: Конеладьи (задача с КИТ-2009).

Если ничего не напутал, то:

1) В каждой строке, как и в каждом столбце может стоять только одна конеладья. (k в таком случае будет порядка min(n, m))
2) На то ставить ли нашу конеладью в очередную клетку влияют только:
   а) занятые столбцы
   b) занята ли строка
   c) где в в предыдущих двух строках расположены конеладьи (таких 2 штуки максимум из-за п. 1)

тогда можно сделать что-то типа такого:
dp[i][usedColumns][where1][where2][cnt]
количество способов расставить cnt конеладьей на первый i строках, с учетом того, что заняты столбцы соответствующие маске usedColumns и в предыдущей строке конеладья находится в столбце where1 (0 - если ее там нет, и 1..n есть), и where2 где находиться конеладья в предпредыдущей строке.
ответ будет sum(dp[n][mask][i][j][k] по всем mask, i, j)

Сложность получается порядка m * 2^n * k * n * n * n = m * 2^n * n^4. Думаю должно пройти.