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

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

Problem A of Gym is giving me a lot of trouble. I have reviewed my code multiple times and after several Wrong Answers I can't see the mistake. Any help is appreciated :) My submission

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

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

You did offset to avoid negative weights, but you actually don't avoid wmax > 802.

For example, in test

10000 500
1 1 100
1 1 100
...
// p[i] = 1, w[i] = 1, d[i] = 100 for all items

You will have in process states with wmax = 500 + 300 + 99 and 500 + 300 + 99 * 2, but your dp has sizes 10002 x 802 x 3. It is not good because you have line in your code:

if(dp[pos][wmax][left] >= 0) return dp[pos][wmax][left];

So you need to change second dimension of dp to m + 2 * 300 or something about it.

P.S. Actually, this code with increasing of second dp dimension gives TL, because check

if(dp[pos][wmax][left] >= 0) return dp[pos][wmax][left];

doesn't return "-INF" results and process "-INF" states every time. You need to change this code to:

if(dp[pos][wmax][left] != -1) return dp[pos][wmax][left];

to process only "-1" states.

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

    Understood! Thank you very much, accepted now :) I will have more care with these "weird jumping" DP excercises the next time.