topcoder: Xscoregame

这一题用递归很简单,直接深度优先搜索所有排序,取最大值即可,但是完全没有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位相同的,已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支,于是求解效率就呈几何级数地提高了。

 

Leave a Reply

Your email address will not be published. Required fields are marked *