正在加载
请稍等

菜单

Home 码农菜园 算法编程 Poj C++: 1011 Sticks
Home 码农菜园 算法编程 Poj C++: 1011 Sticks

Poj C++: 1011 Sticks

算法编程 by   阅读量 3,515

题目链接:http://poj.org/problem?id=1011

一道经典的深度优先搜索算法的实现,一些短木棍片段是由同样长度的若干根长木棍切割而成,求符合要求的长木棍最短可能长度。

最短可能长度显然不小于短木棍片段中最长者,对短木棍首先进行长度逆序排序能大幅缩小搜索空间。从任意一个起点开始搜索,每一步搜索对应的状态量包括当前处理的短木棍序号、再凑成一根长木棍所需长度、当前待处理的短木棍总长度,以及一个全局的记录各个短木棍是否使用的数组变量。

DFS的三点步骤:修改变量、深一层搜索、恢复变量。同时应注意有多个需要及时剪枝的地方,如若不处理将会导致超时。

PS:仅供学习参考,拒绝贴代码刷战绩。

02 2015-11

1条评论

  1. 匿名说道:

    if((sticks[j] == sticks[j – 1] && !used[j – 1]))
    continue;

    这一句可以去掉吗???

发表评论