A knight needs to fight with a queue of people with energy levels P_i and he can fight with two people simultaneously. If the length of the queue is greater than 2, he spends an energy equal to the max of two elements he fights and if he fights with a single person then corresponding energy is spent. While fighting he selects two out of the first three people in the queue and fights.This continues until all the queue is empty. Find the best way to fight with people such that energy is spent min and worst way such that energy is spent max.
I wrote something like this. I got TLE .Can anyone suggest better method. (1<= len(P) <=1000)
def solve (P):
# P is the list of energies of people in the queue
# Write your code here
from collections import defaultdict
dp1 = defaultdict()
def abc(l,time):
k = ' '.join(map(str,l))
if k in dp1:
return dp1[k][0],dp1[k][1]
if len(l)==1:
dp1[k] = [time + l[0],time+l[0]]
return time + l[0],time+l[0]
if len(l)==2:
dp1[k] = [time + max(l),time+max(l)]
return time + max(l),time+max(l)
x1,x2 = abc(l[:1]+l[3:],time+max(l[1],l[2]))
y1,y2 = abc(l[2:],time+max(l[0],l[1]))
dp1[k] = [max(x1,y1),min(x2,y2)]
return max(x1,y1),min(x2,y2)
a,b = abc(P,0)
return b,aComments (1)