小木棍题解.doc

小木棍题解首先要向这题目抱怨一下,花了哥哥我一天啊!写了都快 90 行了, 虽然整理下会少些。声明下 rqnoj 上的数据时错误的, 害我傻傻地一次次地改一次次地纠正乔治有一些同样长的小木棍, 他把这些木棍随意的砍成几段, 直到每段的长都不超过 50 。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。输入文件: 共有二行, 第一行为一个单独的整数 N 表示砍过以后的小木棍的总数,其中 N≤ 60 ,第二行为 N 个用空格隔开的正整数表示 N 根小木棍的长度。输出文件:仅一行表示要求的原始木棍的最小可能长度。 9521521521 思想, 枚举各种肯能出现的原始根数 tot ( 此处可优化) 因为总长度一定 maxx ,所以可得到原始长度 len:=maxx div tot; 接着一根一根地填充原始木棍( dfs (k, nowlen , num )) k 为原始木棍号数。 nowlen 为填充到现在的总长。 num 为砍断后小木棍的号数。将 num 号小棍放入原棍,并记录(记录方法有很多种,我先用了 boolean , 但为了后来的也就是现在用的一种思想, 便改成记录每种边还没用的个数)。当 nowlen=len 是表示一根原棍填充完毕, 刷心 nowlen 继续搜索下一根原棍。当 k=tot 时,即所有圆木棍填充完毕。优化 1 求最大原棍根数 t ,即 maxx 除以小棍的最大值 max 因为原棍必须>=max ; t:=maxx div max; 不过有时最大值可能很小导致 t反而>n 所以这时 t:=n; 优化 2 求从 i到n 的小棍和( b[i]=b[i+1]+a[i] ),在 dfs 中可以优化(例, nowlen+b[num] 时依然小于 len 那么证明不管接下来如何搜索都无法凑成 len 该组合是错误组合优化 3用 total[a[i]] 记录啊 a[i] 出现的次数, 当 total[len-nowlen]>0 证明原棍还差的长度刚好为小棍中某一根的长,那么直接将这根填进去,别小看只是把一层 o(n )变成 1 别忘了,o(n) 中还有下下下下下下层的 o(n), 一下子就少了超多了。优化 4 每根原始木棍填的第一根木棍必须是剩下的最长木棍,因为最后所有小棍都要进到原棍里的嘛! 所以每根原棍必有除去其他原棍后剩下的最长小棍, 我们不过把它提前拿了出来, 让它后面不用再搜到它罢了, 优化效果跟 3 类似, 剪掉超多, 毕竟每一级的 k 的第一级就 o(n) 变1 了。注意: 因为 dfs 中有些小棍是特意放入原棍的,如 3,4 , 过程中没有还原 tota[a[i]] ,所以每种原棍开搜时都得刷新 tota 应该还能有些小优化剪枝, 不过这已经灰常快了, 测了好几个中等数据才 40-60ms ,快吧!不过就是搜得有点蛋疼 var a:array[0..61]of integer;{ 存砍后小棍的长} t,i,j,k,maxx,max,n,len,tot:integer; b:array[0..61]of integer;{ 存排序后从 i到n 根小棍的总长} total,tota:array[0..80]of integer;{ 记录某种小