2008年7月22日星期二

ZJU/ZOJ 1909 Square 解题报告

题目大意是给出m条边的边长，问能否用这些边拼接成一个正方形。

貌似只能DFS。用的剪枝和优化如下：

  1. 如果边长的和不能整除4则必然无解
  2. 如果所求正方形的边长小于已有最大边长则必然无解
  3. 可通过将边长按照从大到小排序，减少搜索时的尝试次数，最优化剪枝
  4. 搜第几条边长只需从第几长的那条边开始搜即可，因为如果前面都无法匹配此时必然也无法匹配

2997030 2008-07-22 18:00:51 Accepted 1909 FPC 00:00.07 408K IwfWcf@LZOI

发帖者 IwfWcf 时间： 18:06:00
标签： ,

1 条评论:

订阅： 博文评论 (Atom)

相关文章

 
Creative Commons License
除非另有声明，本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。