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

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

I am stuck on 8C .Can anyone suggest me how to solve this problem ..?

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

»
11 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Please anybody help ..!!

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

Like the tags of the problem indicate, it's solved by using bitmasks and DP.

  • The state of the DP is the objects put in the handbag so far. You represent these using bitmasks (objects have to be 0-indexed). For example, if you've put objects 0, 3 and 5, the state is 41 (20 + 23 + 25). The size of the DP array will then be 224.
  • Iterate through all the states from 0 to 2N - 1 seeing if adding one or two objects to this state yields a better solution than what you currently have. The cost of adding two objects i and j (potentially the same) is Dist[H][i] + Dist[i][j] + Dist[j][H], where H is the handbag. Dist[i][j] = (x[i] - x[j])2 + (y[i] - y[j])2. Cost[i][i] = 0, obviously.
  • One key observation to make it run in time is that the order in which you put the objects doesn't matter. For example, if the optimal solution is 0 4 3 0 1 0 2 0, it will be the same as 0 1 0 3 4 0 2 0 and the same as 0 1 0 2 0 3 4 0. So, for every state, only consider adding the first object that hasn't been added yet (and maybe another one together with it).
  • To reconstruct the optimal "path", when you find that you can reach state 'y' from state 'x' with optimal cost, store that in an auxiliary array (i.e., From[y] = x).