这一题用递归很简单，直接深度优先搜索所有排序，取最大值即可，但是完全没有DP的思想而且求解时间不可接受；但是如果要DP，如何减少状态数？要知道本题的输入数列排序是影响最终结果的。
下面的解法是DP的，这个DP的妙处在于仍然用输入数列A的子数列组合As作为状态，但是这个状态下面仍然分一些子状态，不过不是用这个子数组的所有排序作为子状态而是用一种hash的方式，即将该子数组的可能结果（子数组每一种排序按题目算法所求得的状态值R=x+x^As[i]）对64（2的6次方）求余所得作为子状态的index。
为什么可以这么做？因为题目中数组A最大的数为50（6bit,可覆盖），所以在一个状态转移到下一状态时，即某个子数组新加入一个元素的时候，其实只需要考虑状态值R的低6位不同的情况即可，因为只有低6位有后效性，只有低6位相同的所有排序只需取最大状态值（这里不用求具体排序，主要求最大值），其他都不用考虑了，而不同的低6位值可能带来不同的有效子状态。说白了，就是当前低6位不一样的，现在不能判定以后谁优谁劣，而当前低6位相同的，已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支，于是求解效率就呈几何级数地提高了。
class Xscoregame:
def getscore(self, a):
s = {(0,0):0}
n = len(a)
ln = 1<<n
for i in range(0, ln):
for j in range(0, 64):
if s.get((i,j), -1) < 0:
continue
for idx,k in enumerate(a):
e = 1 << idx
if e & i > 0:
continue
t = s[(i,j)]
t += t ^ k
ni = i|e
nj = t%64
s[(ni, nj)] = max(s.get((ni, nj),-1), t)
ret = 0
nn = ln - 1
for j in range(0, 64):
ret = max(ret, s.get((nn,j),-1))
return ret
if __name__ == "__main__":
print Xscoregame().getscore([1,2,3])
print Xscoregame().getscore([10,0,0,0])
print Xscoregame().getscore([1,1,1,1,1,1])
print Xscoregame().getscore([1,0,1,0,1,0,1,0])
print Xscoregame().getscore([50,0,1,0,1,0,1,0,1,0,1,0,1,0,1])