随笔 - 6  文章 - 1  trackbacks - 0
<2012年10月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

序列
难度级别: E; 运行时间限制: 3000 ms; 运行空间限制: 65536 KB;代码长度限制: 2000000 B
试题描述
给定M(M<=100)个序列,每个序列N(N<=2000)个非负整数,现在我们要从每个序列选出一个数,一共有N^M种选法,然后我们对从每个序列选出的数求和,得到了N^M个不同的值,我们需要求这当中前N小的值。
输入
第一行M,N
然后M行,每行N个数,代表一个序列
输出
排好序的前N小的数
输入示例
2 3
1 2 3
2 2 3
输出示例
3 3 4

首先DFS有一个顺序性,这个顺序的好坏决定了剪枝的优劣。我们可以注意到此题要求求前N小的组合方案,所以应该基本上选择的都是每个序列中非常靠前的几个数。所以如果说从大的数开始搜索显然效率不好,所以应该把所有序列从小到大排序,这个是剪枝1)。再思考以后发现搜索到第i小的方案后找第i+1小的方案时,有很大可能是把某序列的数向后推了一个,并且这两个数一定是最接近的。所以如果说这种情况发生在搜索的最后一层效率会搞很多。所以我们应该把数与数之间相差最小的排在后面,所以我们可以把所有序列按方差从大到小排序,此为剪枝2)。还有一个剪枝非常明显,如果说此时我们已经搜到的前n小的和中的最大值,比我们现在搜索到位置的和要小,那么如果继续搜索下去不可能找到更小的值,所以直接回溯到上一层,此为简直3)。最后一个剪枝也比较关键,就是如何维护搜到的前n小的数,这时就需要利用堆了,此为剪枝4)。

综上所述,此题可以使用4个剪枝:

1)把所有序列从小到大排序

2)序列之间按方差从大到小排序

3)搜索到某一位置时的和已大于等于已有和的最大值,直接回溯

4)用堆维护前n小的和

1)、3)、4)的剪枝非常重要,用了这些剪枝就可以非常轻松并快速的解决此题。

posted on 2012-10-04 11:20 某科学的魂魄妖梦 阅读(278) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理