Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Just pop randomly each turn ? I don't get the question, please explain!
It's certainly not the obvious greedy strategy of take the biggest of the two ends... counterexample is 1 1 99 2It can definitely be solved by a 2D dynamic program which computes the score of an array [i..j]. S[i, j] is equal to max(a[i]-S[i+1, j], a[j]-S[j-1]), and S[i,i]=a[i]. (hmm, that doesn't tell you Alices actual score, just which decision will lead you to it.)I wonder if there's some fun goofy rule like adding all odd numbers and comparing to all even numbers and not immediately jumping into dynamic programming.
Oh, I got it, bad me.