Привет всем. Нужна ваша помощь по решению задачи (8C - Нахождение порядка). Спасибо за внимание.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
Привет всем. Нужна ваша помощь по решению задачи (8C - Нахождение порядка). Спасибо за внимание.
Название |
---|
Не все не читают теги))
Дам маленькую подсказку. O(N2 * 2N), но на практике всё гораздо меньше.
Можно за O(2n·n). Вообще основная стандартная идея такая. Будем делать динамику по множеству взятых объектов. Хранить множество можно в виде числа. Если представить число в двоичном виде, то можно сказать, что элементы, в разрядах которых стоят единицы, входят в множество, кодируемое данным числом.
Переход в динамике — возьмем один или два предмета. Как взять один ---понятно: переберем удаляемый элемент, посмотрим, что мы насчитали для множества, где этот элемент отсутствует и прибавим квадрат расстояния от него до сумки. Если мы хотим O(2n·n2), то с двумя можно делать примерно то же самое, перебрать их, посмотреть ответ для множества без них и прибавить расстояние, которое нужно пройти, чтобы их собрать (нужно сложить расстояние между этими предметами и расстояния от каждого предмета до сумки).
Теперь, чтобы стало O(2n·n), надо понять, что всегда нужно убирать предмет с самым маленьким номером. То есть, останется перебрать только один предмет из пары. Почему это так? Потому что порядок взятия не важен и когда-то нам в любом случае придется брать этот предмет. Если мы возьмем его сейчас, мы ничего не испортим.
Код: 2039949