CodeForces Beta Round #18 D. Seller Bob

Seller Bob

動的計画法。i日目に2^xMBを手に入れて、j日目に2^xMBのメモリスティックを買いに来る客がいるならば、j日目の収入はj-1日目の収入（この客にメモリスティックを売らない）とi日目の収入+2^xberllar（この客にメモリスティックを売る）のどちらか大きい方。

stick = [-1]*2001
earn = [0]

n = input()

for i in range(1,n+1):

    t = raw_input().split()
    desc,x = t[0],int(t[1])
    
    if desc == "win":
        stick[x] = i
        earn += [earn[i-1]]
        
    if desc == "sell":
        if stick[x] >= 0:
            earn += [max(earn[i-1],earn[stick[x]]+2**x)]
        else:
            earn += [earn[i-1]]

print earn[n]