数学 这里有喜欢 ACM 的同学嘛

u1370943638 · 2013年06月24日 · 最后由 jaxihe 回复于 2014年03月21日 · 9268 次阅读

最近开始喜欢上了 ruby 做 acm

希望有兴趣的人一起在这讨论

http://acm.timus.ru/problem.aspx?space=1&num=1044

可有更快捷的思路? (直接 case-when 算出 4 种答案的数字上去不算哦)

简单思路就是前半和后半都做个表 (其实可以用同一个表)

表的内容是 { 值 => 和为这个值的排列数 }, 然后复杂度就 √n 了

#1 楼 @luikore 你这个并不快吧,生成你所说的 table 是比较慢的。

#2 楼 @zuozuo

我写了个 https://gist.github.com/luikore/5850721 , 就是查表的, 0.1 秒不到

#3 楼 @luikore 这个挺快的 谢谢 :)

这个是个动态规划问题,先用动态规划预处理 i 个数字和为 j 的排列方案数 dp[i][j]. 递推方程为 dp[i][j] = sum { dp[i-1][j-k]} , (0 <= k <= 9} . 长度为 n 的 lucky number 方案总数 ans = sum { dp[half][s] * dp[n-half][s]} ,其中 half = n/2.

c++ 代码见:http://ideone.com/intocY

之前一直用 C++ 做 acm 题,所以就写 c++ 了。。

ruby 写算法,总觉得别扭。。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册