Poj1190 生日蛋糕 — DFS+强力剪枝

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

 

搜索框架没什么可说的，从下往上搜，枚举每层的半径和高度即可。

但是这样朴素的搜索是肯定会超时的，我进行了下面4个有效的剪枝，其中第4个是我没有想出来的，特别强力。

设DFS函数有当前层dep（从上到下为1~m），当前面积s，当前体积v三个参数：procedure dfs(dep,s,v:longint);

 

剪枝一：思维难度：0     剪枝强度：1

对于每次的枚举，肯定要注意边界（枚举范围），其中h和r数组分别记录了前面已经搜到的半径和高度。

for i:=min(trunc(sqrt(n-v)),r[dep+1]-1) downto dep do//半径
for j:=min(trunc((n-v)/(i*i)),h[dep+1]-1) downto dep do//高度

 

剪枝二：思维难度：2     剪枝强度：5（10000 5 的数据从上十秒直降秒杀）

细心的读者可能会注意到上面的循环枚举，用的是downto，这个剪枝你在试验中可以发现。

 

剪枝三：思维难度：3    剪枝强度：3

经过仔细思考可以发现第i层当半径和高度都为i时，有最小面积和最小体积，可预处理出从上往下前i层的最小体积和面积，如果在某一层发现当前体积加上1~dep-1层的最小体积已经大于n，或者当前面积加上1~dep-1的最小面积已经大于已经搜到的ans，那么不再继续搜索。

 

剪枝四：思维难度：5   剪枝强度：4（配合剪枝二使得程序成功AC）

因为dep~m层的体积为v,那么剩余的1~dep-1层的体积满足:
n-v=(h[k]*(r[k]^2)+……+h[1]*(r[1]^2))，其中k=dep-1,……,1
而剩余部分的表面积满足:
lefts=2*(r[k]*h[k]+……+r[1]*h[1])>2*(n-v)/nowr，其中k=dep-1,……,1
显然有上述不等式lefts=ans-s>2*(n-v)/r, 即2*(n-v)/r+s<ans。
所以当2*(n-v)/nowr+s>=ans时也可以进行剪枝。

 

Source Code

Problem: 1190		User: lydliyudong
Memory: 896K		Time: 32MS
Language: Pascal		Result: Accepted

• Source Code

  var
   mins,minv,r,h:array[0..50]of longint;
   n,m,i,ans:longint;
  
  function min(x,y:longint):longint;
   begin
    if x<y then exit(x) else exit(y);
   end;
  
  procedure scanf;
   begin
    readln(n);
    readln(m);
    for i:=1 to 50 do
     begin
      minv[i]:=minv[i-1]+i*i*i;
      mins[i]:=mins[i-1]+2*i*i;
     end;
   end;
  
  procedure dfs(dep,s,v:longint);
   var
    i,j:longint;
   begin
    if dep=0 then
     begin
      if (v=n)and(s<ans) then ans:=s;
      exit;
     end;
    if s>=ans then exit;
    for i:=min(trunc(sqrt(n-v)),r[dep+1]-1) downto dep do//半径
     for j:=min(trunc((n-v)/(i*i)),h[dep+1]-1) downto dep do//高度
      begin
       if (v+i*i*j+minv[dep-1]>n)or(s+2*i*j+mins[dep-1]>ans)or(2*trunc((n-v-i*i*j)/i)+s+2*i*j>=ans) then continue;
       inc(v,i*i*j);
       inc(s,2*i*j);
       if dep=m then inc(s,i*i);
       r[dep]:=i; h[dep]:=j;
       dfs(dep-1,s,v);
       dec(v,i*i*j);
       dec(s,2*i*j);
       if dep=m then dec(s,i*i);
      end;
   end;
  
  begin
   scanf;
   ans:=maxlongint;
   r[m+1]:=maxint; h[m+1]:=maxint;
   dfs(m,0,0);
   if ans=maxlongint then writeln(0) else writeln(ans);
  end.