Блог пользователя vkditya0997

Help !!

Автор vkditya0997, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't get you, Can you please explain?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      The reason that the position should be chosen averagely is Lagrange Multipliers.

      → Ответить