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

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

Hi All,

I am trying this problem. I think it can be solved using Dynamic Programming with bitmasking. Please explain how to approach this problem. I have been able to come up with the following solution but not sure if I am thinking in the right direction.

1) With bitmasking I will look at all the possible combinations of pizzas(from i=1 to i=1<<n).

2) Solution for say i=10010011(written in binary) will be min(solution for (00010011),solution for (10000011),solution for (10010001),solution for (10010010)). When finding solution of 10010011 from 00010011, I will check if the discount are available from the pizzas that are set to 1 in 00010011 and will avail maximum discount possible. For all this I am using 1-D array.

Thanks

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

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

there is 3^15 states. a[i] = 0, if pizza is not bought. a[i] = 1, if pizza i is bought and it's coupon was not used, a[i] = 2 if pizza i is bought and it's coupon was used. About 14 millions of states looks too big, but i think it is author's solution because TL is 5 seconds. use bitmasks for fast checks for coupons.