Hello everyone,
I am trying to solve this problem on topcoder ( SRM 678 div2 1000 ptr )
Not able to get the idea on how to solve!
Please help me in arriving at the solution !
Thanks in advance ! :)
EDIT : Anyone please?
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 20:42:13 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
I'm not sure whether my solution is correct..
First consider if we can shift all these n-1 stairs, we will want to shift them averagely. So we can do a dp[now_stair][shifting_used], make sure that now_stair is not shifted. For transition we enumerate how many stairs after now_stair to be shifted, and shift them to average positions. The time complexity is O(n^4).
I didn't get you, Can you please explain?
Suppose we have 2 stairs, the bottom is 0, the top is 10, and we can shift both of the 2 stairs. Then shifting them to 0, 3, 6, 10 won't be worse than any other shiftings. Like this, in our shifting plan, a consecutive shifted stairs should be averagely placed between the stair before them and the stair after them. So we can use a dp to solve this.
The reason that the position should be chosen averagely is Lagrange Multipliers.