882 - The Mailbox Manufacturers Problem

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

882 - The Mailbox Manufacturers Problem

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 ?
if u can think of it .. u can do it in software.

henrique.renno
New poster
Posts: 6
Joined: Tue Dec 27, 2005 6:13 pm

882 - Mailbox Manufacturers Problem

Hello!!!

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

Thanks for the attention.

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

You can solve problem by using DP

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
New poster
Posts: 1
Joined: Wed Mar 05, 2008 1:36 am
Can you explain how your solution works ? plz

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

This is solution

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.