882 - The Mailbox Manufacturers Problem

[jagadish]

I dont understand how the answer for
5 100 is 495 AFAIK the answer is 449, with the number of crakers taken at each step being:
71
87
94
98
99

But sample i/o is scarcely wrong - have i misunderstood the problem ?

[henrique.renno]

Hello!!!

How can I use DP to solve this problem??? Some ideas?

Thanks for the attention.

[yjwoo14]

I got accept by using DP.

I use 3-dimension matrix.

matrix[k][s][l]

k is capcity the number of mailbox.

s is start the number of crackers

l is length...

so matrix[k][s][l] mean is i have 1 mailbox and..

minimum the number of crackers in range s, s + 1, s+ 2 , .... , (s + l - 1)

sorry I can`t speak english very well

[redghost]

Can you explain how your solution works ? plz

[yjwoo14]

matrix[i][s][l] = max[v = s ~ s + l - 1](matrix[i - 1][s][v - s] + v, matrix[i][v + 1][(s + l) - v - 1] + v)

you can get matrix[i][s][l] mean in before post.