Yes.
http://codepad.org/2KFrv8cs
On Fri, Oct 8, 2010 at 9:56 PM, Lego Haryanto <legoharya...@gmail.com>wrote:
> I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 }
> should be 18, right?
>
> On Thu, Oct 7, 2010 at 10:53 PM, Anand <anandut2...@gmail.com> wrote:
>
>> Using standard Dynamic Programing logic:
>> http://codepad.org/IwBTor4F
>>
>>
>>
>> On Thu, Oct 7, 2010 at 8:43 PM, Gene <gene.ress...@gmail.com> wrote:
>>
>>> Nice problem. Let N_1, N_2, ... N_n be the values of the N notes.
>>> Let F(i,j) be the maximum possible score the current player can get
>>> using only notes i through j. Then
>>>
>>> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>>>
>>> This is saying that the current player always makes the choice that
>>> minimizes B the best score that the other player can achieve. When we
>>> know that choice, the best _we_ can do is the sum of all the available
>>> notes minus B.
>>>
>>> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
>>> where i > j.
>>>
>>> For example, suppose we have notes 3 7 2 1 . The answer we want is
>>> F(1,4).
>>>
>>> Initially we have
>>> F(1,1) = 3
>>> F(2,2) = 7
>>> F(3,3) = 2
>>> F(4,4) = 1
>>>
>>> Now we can compute
>>> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
>>> F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7).
>>> F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2).
>>> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
>>> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
>>> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>>>
>>>
>>> On Oct 7, 8:14 pm, Anand <anandut2...@gmail.com> wrote:
>>> > Given a row of notes (with specified values), two players play a game.
>>> At
>>> > each turn, any player can pick a note from any of the two ends. How
>>> will the
>>> > first player maximize his score? Both players will play optimally.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
