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

UVA-562 — Dividing coins problem getting TLE
Автор ghorardim, история, 7 лет назад, По-английски

I am getting TLE and I can't handle it.I know the is solved by 0-1 Knapsack.I also try this. I think i have some mistake in my code but I do not found it. Please anyone help me..... Problem :UVA-562 — Dividing coins my code :Cpp_Code

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

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

Consider the following test:

100

1 cent 99 times and 500 cents

Your solution will run up to O(2^n) in this case.

Add memo: for each state (i, sum) memoize the answer obtained so that you can get it in O(1) afterwards.

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

    how can i do that???i don't found any idea.

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

      int knap(...)

      if dp[i][sum] is already calculated

      return dp[i][sum];

      if (i == n)

      ...

      ...

      ...

      return dp[i][sum] = max(q1, q2)

      Note that there are some states that will never be reached. So my advice is to do the following thing:

      int knap(...)

      if visited[i][sum] return dp[i][sum]

      if (i == n)...

      visited[i][sum] = true

      ...

      return dp[i][sum] = max(q1, q2)

      → Ответить