> 摘自CDQ作业：
> 搜索, 首先预处理对于每一长度L, 有多少个向量(dx, dy), dx^2 + dy^2 = L^2, 最坏情况下有36个选择的向量.然后进行枚举, 先枚举n!表示线段依次连接的顺序, 再依次枚举每个长度为L线段它对应的向量, 搜索的过程中要及时判断向量是不是顺时针方向偏转的即保证任何时候的折线段是凸的,这样做最坏情况下是720 * 36^6, 考虑优化:
> 1)	不失一般性, 可以假设L1就是第一条摆放的线段, 那么枚举量由6!->5!. 最后一条线段的向量不需要进行枚举, 因为它要回到起点, 36^6->36^5.
> 2)	如果当前的位置(x, y), 与起点(0, 0)的距离要大于剩下的线段长度之和, 那么舍去这个状态.
> 3)	上面两个优化后程序依然很慢, 枚举的状态太多, 而事实上能够构成一个凸包的状态是很少的.我写了个背包, f[i][x][y]表示后i条线段的向量构成是否可以取到向量(x, y),搜索的过程中如果剩下的线段无法达到(-x, -y)这个向量, 状态即可舍去.考虑空间和时间的问题, 我只对最后3个线段作了这个背包, 因此空间为[1 .. 3][-900 .. 900][-900 .. 900], 时间为36^3.
> 有了优化3)后算法的效率就大大提高了, 已经可以在时限内出解了.

• Re:不理解。。。。。。 (0) ccnuzhang 2009-09-23 22:00:32
  • 详细见内 (745) cuiaoxiang 2009-09-23 22:43:49
    • 考虑到边的长度很小，开个950*950的数组记录就可以了吧，好像不用map或者hash (0) Isun 2009-09-26 01:15:42