POJ1011 Sticks — 深搜+剪枝

Note: 本文最初于 2011年02月17日 星期四 21:01 在 hi.baidu.com/lydrainbowcat 发表。

简述个人感想：

做完这道题，我发现我第一次敬佩了Poj！

其实说实在的，在所有常用算法里，我个人认为我掌握的较弱的应该就是搜索，尤其是深搜的剪枝。所以最近一直在练习搜索。

这道题很强大，我在高一上学期里基本没有做过剪枝要求如此强大的DFS题目(就连虫食算跟这题也没法比啊)。

其实这道题一共涉及到3个强力剪枝，这三个少一个都不能AC，我就是少了其中最短的一个——只有一句话一个if语句的剪枝，但是非常强力，所以一直TLE。

这道题我最后是0msAC，用Pascal和C++分别AC了一遍，但是貌似付出了提交10次的代价！

题解：

搜索的过程就不用多说了，框架写出来很简单，就是根据枚举的最终筷子长度，算出有几根，就弄几个栈，然后把筷子往里放。主要看剪枝：

剪枝零：这个还算剪枝么，肯定要先把筷子从大到小排序啊（如果这一点也没想到，你肯定没思考，建议您就不要往下看了，先回去仔细想想）

剪枝一：从小到大规定最终筷子长度，并且只有该长度是长度总和的约数时才进行搜索。——这个是我一眼看出来的，很简单。

剪枝二：不进行重复搜索。也就是用一个变量记录当前刚搜完的筷子的长度，接下来如果有一样的就不要再搜了（由于我们排完序了，一样的肯定和他挨着啊，所以需要一个变量记录就搞定了）。

剪枝三：这个是我一直纠结的地方，这个剪枝是如果第一个木棍都放不进去，那就直接退出false，因为这个当前来说最长的木棍既然这里放不了，那么后边肯定也不行啊！

小技巧：深搜返回类型使用boolean，如果是true就一直退回。

 

Source Code

Problem: 1011		User: lydliyudong
Memory: 900K		Time: 0MS
Language: Pascal		Result: Accepted

• Source Code

  var
   a:array[0..100]of longint;
   v:array[0..100]of boolean;
   n,i,j,sum,max,len,m,p,done:longint;
  
  procedure sort;
   begin
    for i:=1 to n-1 do
     for j:=i+1 to n do
      if a[i]<a[j] then
       begin
        a[i]:=a[i] xor a[j];
        a[j]:=a[i] xor a[j];
        a[i]:=a[i] xor a[j];
       end;
   end;
  
  function dfs(now,last:integer):boolean;
   var
    i:longint;
   begin
    if now=len then
     begin
      last:=1;
      inc(p);
      now:=0;
      done:=0;
      if p=m then exit(true);
     end;
    for i:=last to n do
     begin
      if (now+a[i]<=len)and not v[i] and(done<>a[i]) then
       begin
        inc(now,a[i]);
        v[i]:=true;
        if dfs(now,i+1) then exit(true);
        if now=len then dec(p);
        dec(now,a[i]);
        v[i]:=false;
        done:=a[i];//剪枝二
       end;
      if (last=1)and(not v[i])and(p<>m) then exit(false);//剪枝三，这个剪枝很关键，但是不好想，我就一直因为这个而TLE
     end;
    exit(false);
   end;
  
  begin
   repeat
    readln(n);
    if n=0 then break;
    sum:=0;
    max:=0;
    for i:=1 to n do
     begin
      read(a[i]);
      inc(sum,a[i]);
      if a[i]>max then max:=a[i];
     end;
    sort;
    for i:=max to sum do
     if sum mod i=0 then//剪枝一
      begin
       len:=i;
       m:=sum div i;
       p:=0;
       done:=0;
       fillchar(v,sizeof(v),0);
       if dfs(0,1) then break;
      end;
    writeln(len);
   until seekeof;
  end.