小木棍题解.txt

首先要向这题目抱怨一下,花了哥哥我一天啊!写了都快90行了,虽然整理下会少些。声明下rqnoj上的数据时错误的,害我傻傻地一次次地改一次次地纠正乔治有一些同样长的小木棍,他把这些木棍随意的砍成几段,直到每段的长都不超过50。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。输入文件:共有二行,第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤60,第二行为N个用空格隔开的正整数表示N根小木棍的长度。输出文件:仅一行表示要求的原始木棍的最小可能长度。9 5 21 52 15 21思想,枚举各种肯能出现的原始根数tot(此处可优化)因为总长度一定maxx,所以可得到原始长度len:=maxxdivtot;接着一根一根地填充原始木棍(dfs(k,nowlen,num))k为原始木棍号数。nowlen为填充到现在的总长。num为砍断后小木棍的号数。将num号小棍放入原棍,并记录(记录方法有很多种,我先用了boolean,但为了后来的也就是现在用的一种思想,便改成记录每种边还没用的个数)。当nowlen=len是表示一根原棍填充完毕,刷心nowlen继续搜索下一根原棍。当k=tot时,即所有圆木棍填充完毕。优化1求最大原棍根数t,即maxx除以小棍的最大值max因为原棍必须>=max;t:=maxxdivmax;不过有时最大值可能很小导致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]ofinteger;{记录某种小棍出现的次数,total为模板给tota刷新用的,应为}procedureqsort(x,y:integer);(快排不解释)var s,t,k,tt:integer;begins:=x;t:=y;k:=a[s];repeatwhile(s<t)and(k>=a[t])do dec(t)