One sentence in the problem statement is crucial "your friend will also play optimally", if you interpret it correctly, you are very close to AC. What does it mean? It means, no matter what your current choice is, 1 brick or 2 or 3, your opponent will take optimized score of the rest bricks. Then, it is natural to have a ‘reverse‘ DP:
(thanks to http://massivealgorithms.blogspot.com/2015/01/hackerrank-play-game.html)
t = int(input()) for i in range(t): n = int(input()) arr = [int(i) for i in input().strip().split()] ###### def calc(arr): alen = len(arr) if alen < 4: return sum(arr) ‘‘‘ Both DP[] and PreSum[] is in terms of bottom-up because opponent ‘your friend will also play optimally‘ ‘‘‘ # Calc prefix sum presum = [0] * alen presum[0] = arr[0] for i in range(1, alen): presum[i] = presum[i - 1] + arr[i] # Go DP dp = [0] * (alen) dp[0] = arr[0] dp[1] = arr[1] + dp[0] dp[2] = arr[2] + dp[1] for i in range(3, alen): # Take 1: (i), opponent will take dp[i - 1] x = arr[i] + presum[i - 1] - dp[i - 1] # Take 2 y = presum[i - 2] + arr[i] + arr[i - 1] - dp[i - 2] # Take 3 z = presum[i - 3] + arr[i] + arr[i - 1] + arr[i - 2] - dp[i - 3] dp[i] = max(x, y, z) return dp[alen - 1] ###### # reverse to bottom -> top arr.reverse() print (calc(arr))
原文：http://www.cnblogs.com/tonix/p/4364603.html