LETTers比赛第八场:第三题

  这道题是一道搜索题,不过貌似蛮经典的,网上的解题报告不少。

  这道题可以逐个填充长棒,填完一根再填充下一根。

  这里就只强调一下剪枝策略:

    1. 排序,因为从大到小对棒子进行排序,先填充大棒子,以减少搜索空间;

    2.所求棒的长度一定是总长度的一个约数;

    3.当枚举到第n-1根棒子时,就不用枚举了;

    4.设置标志数组,记录棒子是否被访问过;

    5.去除长度相同的不可用的棒子;

  暂时只能想到这几种剪枝策略,不过推荐一组数据:

64
40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40
40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40
40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40
40

  结果是四百多,一般要是过了这组数据,就应该没有问题了。

  关于这道题,目前能找到的最好的代码在这里

  

原文地址:https://www.cnblogs.com/LETTers/p/2474383.html