小木棍题解.docx

小木棍
(POJ 1011)
【题意描述】
给出N根小木棒(以下称小棒)的长度Li,已知这N根小木棒原本由若干根长
度相同的长木棒(以下称原棒)分解而来。要求出原棒的最小可能长度。
【数据范围】
木棒数N<=64
任意小棒长度Li<=50
【分析一】
思想,枚举各种肯能出现的原始根数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;{记录某种小棍出现的次数,total为模板给tota刷新用的,应为}
procedure qsort(x,y:integer);(快排不解释)
var s,t,k,tt:integer;
begin
s:=x;t:=y;k:=a[s];
repeat
while (s<t)and(k>=a[t]) do dec(t);
if s<t then
begin tt:=a[s];a[s]:=a[t];a[t]:=tt;end;
while (s<t)and(k<=a[s]) do inc(s);
if s>t then
begin tt:=a[s];a[s]:=a[t];a[t]:=tt;end;
until s=t;
a[s]:=k;
if s-1>x then qsort(x,s-1);
if t+1<y then qsort(t+1,y);
end;
function dfs(k,nowlen,num:integer):boolean;
var i,j:integer;
begin
if nowlen+b[num]<len then exit(false);(优化2)
if tota[len-nowlen]>0 then(优化3)
begin
dec(tota[len-nowlen]);
exit(true);
end;
if k=tot then exit(true);
for i:=num to n do
if tota[a[i]]>0 then
if nowlen+a[i]<len then
begin
dec(tota[a[i]]);
if dfs(k,nowlen+a[i],i+1) then exit(true);
inc(tota[a[i]]);
end
else
if nowlen+a[i]=len then
begin
dec(tota[a[i]]);
for j:=1 to n do i