这一题用递归很简单，直接深度优先搜索所有排序，取最大值即可，但是完全没有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位相同的，已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支，于是求解效率就呈几何级数地提高了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
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]) |