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

Help for POI 2018 Round #1 problem: Stone
Автор askhelper, 6 лет назад, По-английски

Hello, all! I need your help for this problem. Basically, we have n vectors originated in (0, 0) and we are to find a subset of these vectors such that length of their sum is maximum.

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

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

Try to think about some optimal solution (and some final point). Which vectors should we use to reach this point?

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

    That makes me think about some kind of dp. For example, if the answer is (x, y) then we need to get $$$(x, y)$$$ or $$$(x - a[1].x, y - a[1].y)$$$ from the vectors 2 to n.

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

      What I'm trying to suggest is that the chosen vectors in the optimal solution have some specific property. Finding this property should later lead to a pretty straightforward solution.

      → Ответить