LightOJ 1223 — Testing Mailboxes (dp) problem needs help.

Revision en2, by Night_Lord, 2020-11-28 12:49:27

Hello,as I am beginner in dp ,I am facing problem with this problem.Anyone help me understand the states and base cases for this problem?

The statement: When monkeys are given some fire-crackers, they have only thing in the mind — to blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k identical mailbox prototypes each fitting up to m fire-crackers. However, he is not sure of how many fire-crackers he needs to provide you with in order for you to be able to solve his problem, so he asks your help.

The constraints are:

  1. If you blow up a mailbox, you can't use the mailbox again, so if you have only k = 1 mailboxes, you would have to start testing with 1 fire-cracker, then 2 fire-crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up even when filled with m fire-crackers, you would need 1 + 2 + 3 + ... + m = m * (m + 1)/2 fire-crackers.

  2. If a mailbox can withstand x fire-crackers, it can also withstand x-1 fire-crackers.

  3. Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

Now the manufacturer wants you to find the maximum number of fire-crackers that his mailboxes can withstand. Before doing that you have to buy some fire-crackers to test that. So, you need to find the minimum number of fire-crackers you need to buy to test the mailboxes.


  Rev. Lang. By When Δ Comment
en2 English Night_Lord 2020-11-28 12:49:27 1530
en1 English Night_Lord 2020-11-26 22:12:46 252 Initial revision (published)