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

Three paths from top left to bottom right?
Автор Mhammad1, история, 9 лет назад, По-английски

Hello everyone

The problem:

Given 2d array with numbers inside each cell, you should maximize the cost to get from top left (1,1) to bottom right (N,M) with three paths, When you pass to cell(i,j) the cost inside it will be removed for the next paths.

You're only allowed to move down or right.

How can I solve something like this?

I've read the tutorial here TopCoder Tutorial but I didn't understand the whole concept.

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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You realise that every time you move downward or to the right, either x or y is increased by 1. So after taking K steps, (x-1) + (y-1) = K.

Therefore, we can represent this DP state as (K, x of first path, x of second path, x of third path) = number of apples received after the first K steps of the three paths. This is O(N^4), which fits the limit of the problem.

Since each x can come from either the same x coordinate or x-1 in the previous diagonal, the transition would be:

f(k, x1, x2, x3) = max(f(k-1, x1, x2, x3), f(k-1, x1, x2, x3-1), f(k-1, x1, x2-1, x3) ... f(k-1, x1-1, x2-1, x3-1)) + (arr[x][k-x] for each unique x among x1, x2, x3)

Therefore we can solve the problem in O(N^4).

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

    Can we use the index of row of x1 so the recurrence will be:

    f(y1, x1, x2, x3) and then we can get the other rows by (y1+x1) ?

    To be more specific, why do we use the steps number not the index of one row?

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

      I think when K >= N, the index of the first row remains at N if I am not mistaken.

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

Note: you can also solve this using mincost maxflow.

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

Can we process the 3 path one after the other i.e. 1. find the path with max cost to get from top,left to bottom,right 2. update the cells covered by previous path as 0 (we have used up all the cost) 3. repeat #1 and #2 for second and third path

I don't think the choice of path1 affects path2 and so on, since they wouldn't intersect. What do you guys think?

→ Ответить