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位相同的,已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支,于是求解效率就呈几何级数地提高了。

 

topcoder: YetAnotherORProblem2

这题显示只有18%的AC率,题目本身不难,估计都是败在执行时间上了;我的解法如下,典型的DP思维,子问题是:如果已知长度为n-1的情况下,和或操作相等的数列,求长度为n的情况;状态index为每个满足条件的数列的和Sn-1(因为和或相等,也是该数列的或),状态值为该index对应的数列有多少种。状态转移方程为:

if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]

 

topcoder: YetAnotherTwoTeamsProblem

这是一道标记为hard的题,确实比较hard

开始用了一个比较简单暴力的方法,其实也是DP思路,但是状态取的比较偷懒,直接用了所有的可能组合作为状态,虽然在求解过程中可以利用到已经搜索过的状态,但是整个搜索空间还是太大了,导致虽然结果正确,但是严重超时了:

又做了一次伸手党,看了解答后醒悟了,其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。 点我展开分析内容

topcoder: ZigZag

再来水一道简单题:题目地址

想法很自然,记录下当前的方向,一旦出现方向不一致的就把总数加一,同时方向改变,否则continue,然而其实已经包含了动态规划思想

上代码:

看了下别人提交的,思路一样,只不过有人上来先把整个序列的变化趋势算一遍,即遍历seq,然后算出seq[i]-seq[i-1]的值记录下来记为V[i],其实要的就是一个正负号,然后再次遍历还是记录当前的方向,乘以当前遍历到的那个趋势V[i],乘积发生变化时就在结果上加一并改变当前方向值。

topcoder practice: ZooExchangeProgram

为了兴趣,也为了保持coding的能力,重新开始写一些算法题;为了对算法了解的更透彻,也为了锻炼表达能力,干脆在博客里面对解题代码进行详解,代码是自己写的,但也不排除参考了别人的解法,消化吸收了就是自己的,不是吗?

题面:

太长了,就不贴了,链接在此

代码及详解: