Лучше поздно чем никогда
Сегодня, 30 ноября, состоялся очередной СРМ
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 173 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Скорее всего венгерский алгоритм (ну или парасочетание с помощью минкоста).
Каждой фигуре из начального состояния соответствует какая-то фигура из конечного. таким образом для каждой пары фигур можно определить сколько понадобится ходов для перехода.
А что делать, когда все кони уже стоят на своих местах, но их надо подвинуть, чтобы пропустить пешку?
Пример 1:
...
.N.
.P.
---
.P..
.N.
...
Пример 2:
..P.P..
.P...P.
...N...
.P.P.P.
..P.N..
.......
-------
..P.P..
.P.P.P.
...N...
.P...P.
..P.N..
.......
Я вот тоже думаю как решать. Оценка сверху количества позиций не такая и хорошая:
Но может решение и есть простой бфс, это же див2 всё-таки.
Параметры: номер обрабатываемой вершинки, текущая сумма длин внутри объединенных вершин, текущее количество объединенных вершин.
Отсортируем деревья по возрастанию r.
Представим что перестановка это такой граф-цикл из N+1 вершины. Чтобы получить по графу перестановку надо разрезать цикл по N+1-ой вершинке. Вес ребра i-j в графе это rmax(i, j)
Представим себе следующий разрез: вершины с 1 по i в одной части, i + 1 по N в другой. Пусть через этот разрез проходит s пар рёбер. Будем считать число вариантов соединений в левой части разреза.
Три параметра: i - текущая вершинка которую мы переносим через разрез, s - сколько пар рёбер есть в разрезе (проходит из одной части в другую), w - текущая длина перестановки, если учесть все рёбра между вершинами 1..(i - 1).
Значение - количество графов оказывающихся в "левой" части разреза.
Внутри надо перебрать сколько рёбер ведёт из вершины i налево, а сколько направо. Варианты:
2-0 : таких вариантов s * (s - 1) * 2, при этом s надо уменьшать на 1. Вес увеличивается на 2ri
1-1 : таких вариантов ровно s, при этом s не меняется. Вес увеличивается на ri
0-2 : вариант один, s увеличивается на 1.