posts - 13, comments - 0, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 4.3.2 The Primes

Posted on 2009-03-08 11:35 杜仲当归 阅读(344) 评论(0)  编辑 收藏 引用
一道相当BT的搜索题,写了300+行数。更BT的是前前后后写了五六遍,几种搜索策略都离通过最后两个点差之毫厘,最终还是加了剪枝才过的。一道题写了1K行以上的代码量,也算是罕古未见了!

此题首先要明确搜索顺序。限制条件最多的是第五行和第五列,然后对角线也可以控制较多行列,之后是第一行和第一列,最后减法得到剩下四个数,判断即可。

但是这样仍然过不了23 7这样的数据。于是加入剪枝:在搜索完第五行第五列的同时,发现有四行已经填上了三个数,且都是X3X77这样的排列。因此可以预先建立表,判断出第2,4,5位已知的数是否可能为质数,不满足者剪枝。

在搜索每一行列的时候注意已填入的信息,为此要建立已知第1位,第3位,第5位的质数表。

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