USACO March 2006 Gold : tselect : Passed
Debug了非常,非常长的时间(应该有1x小时了),tselect终于通过了所有数据(Slowest:8 0.577 secs)第一次做多叉树转二叉树的DP,而且还是关于边的……多叉树转二叉树是麻烦的,关于边的是麻烦的,所以这道题是特别麻烦的……Debug的时候发现很多思路不清的地方,关键是一开始要下好定义,这样接下去才不会乱……最后算法对了之后,8,9,10超时,解决办法是先做一下小的DP(7、8行),算出每个节点最多承受几条边,也就是边数上限,用这个上限来约束,很快就出来了。另,可以不二分的(按我的做法,二分会出问题的,因为不是单调的,所以用枚举,结果枚举也很快,基本上只有枚举第一个的时候花时间,后面都是直接调用)。希望SHTSC不会这样!……(树的双中心已经很恶心了……)